提交记录 9286


用户 题目 状态 得分 用时 内存 语言 代码长度
Dispwnl noip18d. 【NOIP2018】旅行 Accepted 100 537.557 ms 772 KB C++ 1.54 KB
提交时间 评测时间
2019-04-22 16:46:58 2020-08-01 01:35:21
// luogu-judger-enable-o2
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
using namespace std;
const int MAX=1e4+5;
struct p{
    int x;
    bool operator< (const p &a)
    const{
        return x<a.x;
    }
};
struct q{
    int x,y;
}s[MAX];
int n,m,num,tot,s1,s2;
int h[MAX],ans[MAX],qu[MAX],Ans[MAX];
vector<p> c[MAX];
bool use[MAX];
bool look(int x,int y)
{
    if(s1==x&&s2==y) return 1;
    if(s1==y&&s2==x) return 1;
    return 0;
}
void Change()
{
    for(int i=1;i<=n;++i)
      if(Ans[i]&&Ans[i]<ans[i]) return;
      else if((Ans[i]&&Ans[i]>ans[i])||!Ans[i])
      {
      	for(int j=1;j<=n;++j)
      	  Ans[j]=ans[j];
      	return;
      }
}
void dfs(int x,int fa)
{
    int siz=c[x].size();
    use[x]=1,ans[++tot]=x;
    for(int i=0;i<siz;++i)
      if(c[x][i].x!=fa&&!use[c[x][i].x]&&!look(x,c[x][i].x)) dfs(c[x][i].x,x);
}
int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;++i)
      scanf("%d%d",&x,&y),c[x].push_back((p){y}),c[y].push_back((p){x}),s[i].x=x,s[i].y=y;
    for(int i=1;i<=n;++i)
      sort(c[i].begin(),c[i].end());
    if(m==n-1)
    {
        dfs(1,0);
        for(int i=1;i<=n;++i)
          printf("%d ",ans[i]);
    }
    else
    {
        for(int i=1;i<=m;++i)
          {
          	memset(use,0,sizeof(use));
          	s1=s[i].x,s2=s[i].y,tot=0;
          	dfs(1,0);
            if(tot==n) Change();
          }
        for(int i=1;i<=n;++i)
          printf("%d ",Ans[i]);
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #171.4 us288 KBAcceptedScore: 4

Testcase #277.31 us288 KBAcceptedScore: 4

Testcase #370.6 us288 KBAcceptedScore: 4

Testcase #496.77 us296 KBAcceptedScore: 4

Testcase #596.76 us296 KBAcceptedScore: 4

Testcase #6355.79 us376 KBAcceptedScore: 4

Testcase #7355.4 us380 KBAcceptedScore: 4

Testcase #8356.95 us384 KBAcceptedScore: 4

Testcase #9361.51 us364 KBAcceptedScore: 4

Testcase #10360.9 us356 KBAcceptedScore: 4

Testcase #111.624 ms668 KBAcceptedScore: 4

Testcase #121.614 ms720 KBAcceptedScore: 4

Testcase #131.609 ms736 KBAcceptedScore: 4

Testcase #141.607 ms668 KBAcceptedScore: 4

Testcase #151.614 ms772 KBAcceptedScore: 4

Testcase #1673.37 us292 KBAcceptedScore: 4

Testcase #1774.73 us292 KBAcceptedScore: 4

Testcase #18167.83 us304 KBAcceptedScore: 4

Testcase #19170.78 us300 KBAcceptedScore: 4

Testcase #2011.467 ms400 KBAcceptedScore: 4

Testcase #2111.563 ms400 KBAcceptedScore: 4

Testcase #2211.819 ms400 KBAcceptedScore: 4

Testcase #23537.557 ms768 KBAcceptedScore: 4

Testcase #24535.377 ms752 KBAcceptedScore: 4

Testcase #25536.448 ms740 KBAcceptedScore: 4


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