提交记录 11531


用户 题目 状态 得分 用时 内存 语言 代码长度
boboy noip18d. 【NOIP2018】旅行 Accepted 100 578.071 ms 676 KB C++ 1.91 KB
提交时间 评测时间
2020-01-26 11:48:10 2020-08-01 02:45:03
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
inline int read(){
	int ans=0;
	char a=getchar();
	while('0'>a||a>'9'){
		a=getchar();
	}
	while('0'<=a&&a<='9'){
		ans=ans*10+a-'0';
		a=getchar();
	}
	return ans;
}
vector<int>edge[5005];
struct node{
	int next,tot;
};
vector<node>edge1[5005];
int n,m;
int out[5005],fst[5005],nout[5005],now,cut;
bool been[5005];
void dfs(int u){
	been[u]=1;
	for(int i=0;i<edge[u].size();i++){
		int v=edge[u][i];
		if(!been[v]){
			nout[now++]=v;
			dfs(v);
		}
	}
}
void dfs1(int u){
	been[u]=1;
	for(register int i=0;i<edge1[u].size();i++){
		node v=edge1[u][i];
		if(v.tot==cut)continue;
		if(been[v.next]==0){
			nout[now++]=v.next;
			dfs1(v.next);
		}
	}
}
inline bool cmp(node x,node y){
	return x.next<y.next;
}
int main(){
	n=read(),m=read();
	if(n-1==m){
		for(int i=1;i<=m;i++){
			int x=read(),y=read();
			edge[x].push_back(y);
			edge[y].push_back(x);
		}
		for(int i=1;i<=n;i++){
			sort(edge[i].begin(),edge[i].end());
		}
		fst[1]=-1;
		now=2;
		nout[1]=1;
		dfs(1);
		for(int i=1;i<=n;i++){
			printf("%d ",nout[i]);
		}
	}
	else{
		for(register int i=1;i<=m;i++){
			int x=read(),y=read();
			edge1[x].push_back(node{y,i});
			edge1[y].push_back(node{x,i});
		}
		for(register int i=1;i<=n;i++){
			sort(edge1[i].begin(),edge1[i].end(),cmp);
		}
		bool flag=0;
		for(cut=1;cut<=m;cut++){
			memset(been,0,sizeof(been));
			nout[1]=1;
			now=2;
			dfs1(1);
			if(now>n){
				if(!flag){
					for(int i=1;i<=n;i++){
						out[i]=nout[i];
					}
				}
				else{
					bool flag1=1;
					for(register int i=1;i<=n;i++){
						if(nout[i]>out[i]){
							flag1=0;
							break;
						}
						if(nout[i]<out[i])break;
					}
					if(flag1){
						for(int i=1;i<=n;i++){
							out[i]=nout[i];
						}
					}
				}
				flag=1;
			}
		}
		for(register int i=1;i<=n;i++){
			printf("%d ",out[i]);
		}
		puts("");
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #175.16 us280 KBAcceptedScore: 4

Testcase #279.4 us280 KBAcceptedScore: 4

Testcase #373.33 us280 KBAcceptedScore: 4

Testcase #497.92 us284 KBAcceptedScore: 4

Testcase #596.47 us284 KBAcceptedScore: 4

Testcase #6326.22 us348 KBAcceptedScore: 4

Testcase #7329.73 us352 KBAcceptedScore: 4

Testcase #8328.5 us356 KBAcceptedScore: 4

Testcase #9334.37 us340 KBAcceptedScore: 4

Testcase #10333.48 us336 KBAcceptedScore: 4

Testcase #111.473 ms576 KBAcceptedScore: 4

Testcase #121.48 ms616 KBAcceptedScore: 4

Testcase #131.474 ms628 KBAcceptedScore: 4

Testcase #141.467 ms576 KBAcceptedScore: 4

Testcase #151.469 ms656 KBAcceptedScore: 4

Testcase #1677.22 us280 KBAcceptedScore: 4

Testcase #1774.95 us280 KBAcceptedScore: 4

Testcase #18169.63 us284 KBAcceptedScore: 4

Testcase #19170.72 us284 KBAcceptedScore: 4

Testcase #2011.141 ms364 KBAcceptedScore: 4

Testcase #2111.293 ms364 KBAcceptedScore: 4

Testcase #2211.576 ms364 KBAcceptedScore: 4

Testcase #23574.598 ms676 KBAcceptedScore: 4

Testcase #24576.931 ms668 KBAcceptedScore: 4

Testcase #25578.071 ms660 KBAcceptedScore: 4


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