提交记录 11199


用户 题目 状态 得分 用时 内存 语言 代码长度
SkyWT noip18d. 【NOIP2018】旅行 Accepted 100 908.703 ms 20512 KB C++ 1.64 KB
提交时间 评测时间
2019-11-05 21:54:14 2020-08-01 02:40:04
#include<bits/stdc++.h>

using namespace std;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

const int maxn=5005,maxe=10005;

int n,m;
int tot=0,lnk[maxn],nxt[maxe],to[maxe];
pair<int,int> edges[maxn];
bool vis[maxn];

int ans[maxn],now[maxn];
pair<int,int> now_block;

int son[maxn][maxn];

void add_edge(int x,int y){
	tot++; to[tot]=y;
	nxt[tot]=lnk[x];lnk[x]=tot;
}

bool check(int x,int y){
	if (x==now_block.first && y==now_block.second) return false;
	if (y==now_block.first && x==now_block.second) return false;
	return true;
}

void DFS(int x){
	vis[x]=true; now[++now[0]]=x;
	for (int i=1;i<=son[x][0];i++)
		if (!vis[son[x][i]] && check(x,son[x][i])) DFS(son[x][i]);
}

bool smaller(){
	for (int i=1;i<=n;i++)
		if (now[i]<ans[i]) return true; else
		if (now[i]>ans[i]) return false;
	return false;
}

int main(){
	#ifdef DEBUG
		freopen("testdata.in","r",stdin);
		freopen("my.out","w",stdout);
	#endif
	n=read();m=read();
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		add_edge(x,y);add_edge(y,x);
		son[x][++son[x][0]]=y;
		son[y][++son[y][0]]=x;
		edges[i]=make_pair(x,y);
	}
	for (int i=1;i<=n;i++) sort(son[i]+1,son[i]+1+son[i][0]);

	if (m==n-1){
		DFS(1);
		for (int i=1;i<=n;i++) printf("%d ",now[i]);
		printf("\n");
	} else {
		for (int i=1;i<=m;i++){
			memset(vis,0,sizeof(vis));
			now_block=edges[i]; now[0]=0;
			DFS(1);
			if (now[0]!=n) continue;
			if (ans[0]==0 || smaller())
				for (int j=0;j<=n;j++) ans[j]=now[j];
		}
		for (int i=1;i<=n;i++) printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #145.11 us104 KBAcceptedScore: 4

Testcase #250.32 us104 KBAcceptedScore: 4

Testcase #351.54 us104 KBAcceptedScore: 4

Testcase #4101.61 us468 KBAcceptedScore: 4

Testcase #5101.69 us468 KBAcceptedScore: 4

Testcase #6686.33 us4 MB + 48 KBAcceptedScore: 4

Testcase #7688.78 us4 MB + 52 KBAcceptedScore: 4

Testcase #8687.7 us4 MB + 56 KBAcceptedScore: 4

Testcase #9692.39 us4 MB + 32 KBAcceptedScore: 4

Testcase #10694.53 us4 MB + 24 KBAcceptedScore: 4

Testcase #113.609 ms19 MB + 960 KBAcceptedScore: 4

Testcase #123.617 ms19 MB + 1000 KBAcceptedScore: 4

Testcase #133.605 ms19 MB + 1012 KBAcceptedScore: 4

Testcase #143.6 ms19 MB + 948 KBAcceptedScore: 4

Testcase #153.612 ms20 MB + 20 KBAcceptedScore: 4

Testcase #1647.13 us108 KBAcceptedScore: 4

Testcase #1747.16 us108 KBAcceptedScore: 4

Testcase #18179.32 us480 KBAcceptedScore: 4

Testcase #19178.86 us476 KBAcceptedScore: 4

Testcase #2012.59 ms4 MB + 72 KBAcceptedScore: 4

Testcase #2112.484 ms4 MB + 72 KBAcceptedScore: 4

Testcase #2212.816 ms4 MB + 72 KBAcceptedScore: 4

Testcase #23908.703 ms20 MB + 32 KBAcceptedScore: 4

Testcase #24899.358 ms20 MB + 8 KBAcceptedScore: 4

Testcase #25892.474 ms19 MB + 1012 KBAcceptedScore: 4


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