提交记录 7874


用户 题目 状态 得分 用时 内存 语言 代码长度
Panda_hu noip18d. 【NOIP2018】旅行 Accepted 100 707.598 ms 35868 KB C++ 1.50 KB
提交时间 评测时间
2019-01-25 19:16:44 2020-08-01 01:09:34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 5000
struct node
{
    int u,v;
}a[MAXN+5];
int n,m;
int vis[MAXN+5],ans[MAXN+5],seq[MAXN+5],top;
vector<int> G[MAXN+5];
int Gr[MAXN+5][MAXN+5];
void dfs(int x)
{
    vis[x]=1;
    seq[++top]=x;
    for(int i=0;i<G[x].size();i++)
        {
            int xnt=G[x][i];
            if(vis[xnt]||!Gr[x][xnt])continue;
            dfs(xnt);
        }
}
int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ans[i]=n+1;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        a[i].u=u,a[i].v=v;
        G[u].push_back(v);
        G[v].push_back(u);
        Gr[u][v]=1;
        Gr[v][u]=1;
    }
    for(int i=1;i<=n;i++)
    sort(G[i].begin(),G[i].end());
    if(n==m)
    for(int i=1;i<=m;i++)
    {
        top=0;
        for(int j=1;j<=n;j++)
        vis[j]=0;
        Gr[a[i].u][a[i].v]=0;
        Gr[a[i].v][a[i].u]=0;
        dfs(1);
        Gr[a[i].u][a[i].v]=1;
        Gr[a[i].v][a[i].u]=1;
        if(top<n)continue;
        int F=1;
        for(int j=1;j<=n;j++)
        if(ans[j]>seq[j])break;
        else if(ans[j]<seq[j]){F=0;break;}
        if(F)
        {
            for(int j=1;j<=n;j++)
            ans[j]=seq[j];
        }
    }
    else 
    {
        dfs(1);
        for(int i=1;i<=n;i++)
        ans[i]=seq[i];
    }
    for(int i=1;i<=n;i++)
    printf("%d ",ans[i]);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #160.1 us212 KBAcceptedScore: 4

Testcase #267.04 us212 KBAcceptedScore: 4

Testcase #360.54 us212 KBAcceptedScore: 4

Testcase #4115.94 us584 KBAcceptedScore: 4

Testcase #5106.84 us584 KBAcceptedScore: 4

Testcase #6651.62 us5 MB + 372 KBAcceptedScore: 4

Testcase #7658.43 us5 MB + 480 KBAcceptedScore: 4

Testcase #8662.33 us5 MB + 544 KBAcceptedScore: 4

Testcase #9653.89 us5 MB + 224 KBAcceptedScore: 4

Testcase #10652.32 us5 MB + 212 KBAcceptedScore: 4

Testcase #113.675 ms34 MB + 416 KBAcceptedScore: 4

Testcase #123.694 ms34 MB + 712 KBAcceptedScore: 4

Testcase #133.69 ms34 MB + 872 KBAcceptedScore: 4

Testcase #143.668 ms34 MB + 360 KBAcceptedScore: 4

Testcase #153.706 ms35 MB + 28 KBAcceptedScore: 4

Testcase #1661.45 us212 KBAcceptedScore: 4

Testcase #1760.28 us212 KBAcceptedScore: 4

Testcase #18169.81 us588 KBAcceptedScore: 4

Testcase #19171.32 us580 KBAcceptedScore: 4

Testcase #2011.929 ms5 MB + 396 KBAcceptedScore: 4

Testcase #2111.886 ms5 MB + 560 KBAcceptedScore: 4

Testcase #2212.2 ms5 MB + 492 KBAcceptedScore: 4

Testcase #23707.598 ms34 MB + 896 KBAcceptedScore: 4

Testcase #24705.92 ms34 MB + 584 KBAcceptedScore: 4

Testcase #25703.617 ms34 MB + 452 KBAcceptedScore: 4


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