提交记录 11199


用户 题目 状态 得分 用时 内存 语言 代码长度
SkyWT noip18d. 【NOIP2018】旅行 Accepted 100 839.534 ms 19 MB + 1012 KB C++ 1.64 KB
提交时间 评测时间
2019-11-05 21:54:14 2019-12-29 22:51:41
#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 #136.5 us116 KBAcceptedScore: 4

Testcase #235.26 us116 KBAcceptedScore: 4

Testcase #337.31 us116 KBAcceptedScore: 4

Testcase #486.81 us484 KBAcceptedScore: 4

Testcase #591.28 us484 KBAcceptedScore: 4

Testcase #6590.29 us4 MB + 52 KBAcceptedScore: 4

Testcase #7592.48 us4 MB + 56 KBAcceptedScore: 4

Testcase #8588.47 us4 MB + 56 KBAcceptedScore: 4

Testcase #9676.66 us4 MB + 40 KBAcceptedScore: 4

Testcase #10602.98 us4 MB + 36 KBAcceptedScore: 4

Testcase #113.126 ms19 MB + 932 KBAcceptedScore: 4

Testcase #123.123 ms19 MB + 964 KBAcceptedScore: 4

Testcase #133.109 ms19 MB + 976 KBAcceptedScore: 4

Testcase #143.183 ms19 MB + 920 KBAcceptedScore: 4

Testcase #153.123 ms19 MB + 1012 KBAcceptedScore: 4

Testcase #1640.66 us120 KBAcceptedScore: 4

Testcase #1739.33 us120 KBAcceptedScore: 4

Testcase #18164.19 us488 KBAcceptedScore: 4

Testcase #19163.56 us488 KBAcceptedScore: 4

Testcase #2012.786 ms4 MB + 72 KBAcceptedScore: 4

Testcase #2112.71 ms4 MB + 72 KBAcceptedScore: 4

Testcase #2213.034 ms4 MB + 72 KBAcceptedScore: 4

Testcase #23839.534 ms19 MB + 1008 KBAcceptedScore: 4

Testcase #24838.015 ms19 MB + 1004 KBAcceptedScore: 4

Testcase #25833.302 ms19 MB + 980 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-04-06 09:59:24 | Loaded in 102 ms | Server Status
个人娱乐项目,仅供学习交流使用