提交记录 9225


用户 题目 状态 得分 用时 内存 语言 代码长度
namespace_std noip18d. 【NOIP2018】旅行 Accepted 100 10.621 ms 44252 KB C++ 2.04 KB
提交时间 评测时间
2019-04-20 10:56:00 2020-08-01 01:34:35
#include<cstdio>
#include<cstring>
#include<queue>
bool isin[5555];
int n,m;
struct edge
{int p,t;bool flag;}e[22222];
int asw[5555],tot,h[5555];
inline void build(int x,int y)
{e[++tot]=(edge){h[x],y,0},h[x]=tot;}
int low,from[5555],d[5555];
int tp,stk[5555];
bool vis[5555];
int argv[5555][5555];
int argc[5555];
bool flag[5555][5555];
std::priority_queue<int>Q;
inline int dfs(int s=1,bool need=1)
{
    stk[++tp]=s;
    if(stk[tp]<asw[tp])need=0;
    if(need&&(stk[tp]>asw[tp]))return 0;
    vis[s]=1;
    for(register int i=1;i<=argc[s];i++)
    {
        int to=argv[s][i];
        if(flag[s][to])continue;
        if(vis[to])continue;
        int t=dfs(to,need);
        if(!t)return 0;
        else if(t==2)need=0;
    }if(!need)return 2;
    else return 1;
}
int x[5555],y[5555];
inline void cnter()
{
    register int i,ii,iii;
    for(i=1;i<=n;i++)
    {
        for(ii=h[i];ii;ii=e[ii].p)
        {
            int to=e[ii].t;
            Q.push(-to);
        }
        for(;Q.size();)
        {argv[i][++argc[i]]=-Q.top();Q.pop();}
    }
    asw[1]=2;
    if(m==n-1)
    {
        dfs();
        for(i=1;i<=n;i++)
            asw[i]=stk[i];
    }
    else
    {
        for(i=1;i<=m;i++)
        {
            tp=0;
            flag[x[i]][y[i]]=flag[y[i]][x[i]]=1;
            memset(vis,0,sizeof(vis));
            dfs();
            if(tp==n)
            {
                for(ii=1;ii<=n;ii++)
                {
                    if(asw[ii]>stk[ii])
                    {
                        for(iii=1;iii<=n;iii++)
                            asw[iii]=stk[iii];
                        break;
                    }
                    else if(asw[ii]<stk[ii])break;
                }
            }
            flag[x[i]][y[i]]=flag[y[i]][x[i]]=0;
        }
    }
    for(i=1;i<n;i++)
        printf("%d ",asw[i]);
    printf("%d\n",asw[n]);
}
int main()
{
    register int i;
    scanf("%d%d",&n,&m);
    isin[1]=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        d[x[i]]++,d[y[i]]++;
        build(x[i],y[i]),build(y[i],x[i]);
    }
    cnter();
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #123.42 us108 KBAcceptedScore: 4

Testcase #225.85 us108 KBAcceptedScore: 4

Testcase #323.26 us108 KBAcceptedScore: 4

Testcase #485.88 us480 KBAcceptedScore: 4

Testcase #585.47 us472 KBAcceptedScore: 4

Testcase #6738.43 us4 MB + 84 KBAcceptedScore: 4

Testcase #7738.72 us4 MB + 88 KBAcceptedScore: 4

Testcase #8740.13 us4 MB + 92 KBAcceptedScore: 4

Testcase #9733.68 us4 MB + 64 KBAcceptedScore: 4

Testcase #10733.86 us4 MB + 60 KBAcceptedScore: 4

Testcase #113.827 ms20 MB + 48 KBAcceptedScore: 4

Testcase #123.841 ms20 MB + 100 KBAcceptedScore: 4

Testcase #133.865 ms20 MB + 136 KBAcceptedScore: 4

Testcase #143.823 ms20 MB + 48 KBAcceptedScore: 4

Testcase #153.87 ms20 MB + 176 KBAcceptedScore: 4

Testcase #1626.59 us148 KBAcceptedScore: 4

Testcase #1726.97 us148 KBAcceptedScore: 4

Testcase #18123.06 us880 KBAcceptedScore: 4

Testcase #19123.94 us880 KBAcceptedScore: 4

Testcase #201.316 ms8 MB + 280 KBAcceptedScore: 4

Testcase #211.295 ms8 MB + 336 KBAcceptedScore: 4

Testcase #2210.621 ms8 MB + 360 KBAcceptedScore: 4

Testcase #238.3 ms43 MB + 220 KBAcceptedScore: 4

Testcase #247.526 ms42 MB + 940 KBAcceptedScore: 4

Testcase #256.359 ms42 MB + 804 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 12:51:00 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用