提交记录 12857


用户 题目 状态 得分 用时 内存 语言 代码长度
luosiyuan noip18d. 【NOIP2018】旅行 Time Limit Exceeded 88 1 s 59992 KB C++11 1.88 KB
提交时间 评测时间
2020-06-13 19:44:07 2020-08-01 03:00:23
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Edge{
	int to,next;
}e[10005];
int prt[5005],h[5005],cnt=1,n,m,used[5005],fa[5005],inans[5005],sss;
vector<int> a;
vector<int> ans[5005];
void Add_Edge(int x,int y){
	e[++cnt].to=y;
	e[cnt].next=h[x];
	h[x]=cnt;
}
void dfs2(int point){
	if(used[point]&&prt[point]){
		dfs2(prt[point]);
		return ;
	}
	if(!inans[point])a.push_back(point),inans[point]=1;
	vector<int>tmp;
	for(int i=h[point];i;i=e[i].next){
		int y=e[i].to;
		if(!used[y]&&y!=prt[point])tmp.push_back(y);
	}
	used[point]=1;
	sort(tmp.begin(),tmp.end());
	for(int i=0;i<tmp.size();i++)dfs2(tmp[i]);
	if(!used[prt[point]])dfs2(prt[point]);
	used[point]=0;
}
void dfs1(int point,int nx,int ny){
	if(used[point])return ;
	used[point]=1;
	a.push_back(point);
	vector<int> vec;
//	cout<<"now:"<<point<<endl;
	for(int i=h[point];i;i=e[i].next){
		int y=e[i].to;
		if(!used[y]&&!((point==nx&&y==ny)||(point==ny&&y==nx)))vec.push_back(y);//,cout<<y<<' ';
	}
//	puts("");
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)dfs1(vec[i],nx,ny);
}
bool usedb[10005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		Add_Edge(x,y);
		Add_Edge(y,x);
	}
	if(m==n-1){
		used[0]=1;
		dfs2(1);
		for(int i=0;i<n;i++)cout<<a[i]<<' ';
	}
	else {
		for(int i=1;i<=n;i++){
			for(int j=h[i];j;j=e[j].next){
				if(usedb[j])continue;
				usedb[j]=usedb[j^1]=1;
				memset(used,0,sizeof(used));
				//cout<<"duanbian:"<<i<<' '<<e[j].to<<endl;
				dfs1(1,i,e[j].to);
				if(a.size()==n)ans[++sss]=a;
				//for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
				//cout<<endl;
				a.clear();
			}
		}
		sort(ans+1,ans+sss+1);
		for(int i=0;i<ans[1].size();i++)cout<<ans[1][i]<<' ';
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #163.8 us176 KBAcceptedScore: 4

Testcase #267.95 us176 KBAcceptedScore: 4

Testcase #367.42 us176 KBAcceptedScore: 4

Testcase #482.16 us184 KBAcceptedScore: 4

Testcase #581.03 us184 KBAcceptedScore: 4

Testcase #6233.64 us324 KBAcceptedScore: 4

Testcase #7234.17 us336 KBAcceptedScore: 4

Testcase #8232.2 us340 KBAcceptedScore: 4

Testcase #9252.55 us284 KBAcceptedScore: 4

Testcase #10252.36 us276 KBAcceptedScore: 4

Testcase #111.066 ms704 KBAcceptedScore: 4

Testcase #121.057 ms844 KBAcceptedScore: 4

Testcase #131.032 ms872 KBAcceptedScore: 4

Testcase #141.042 ms696 KBAcceptedScore: 4

Testcase #151.034 ms968 KBAcceptedScore: 4

Testcase #1672.48 us192 KBAcceptedScore: 4

Testcase #1770.77 us192 KBAcceptedScore: 4

Testcase #18499.27 us224 KBAcceptedScore: 4

Testcase #19468.62 us220 KBAcceptedScore: 4

Testcase #2030.758 ms4 MB + 188 KBAcceptedScore: 4

Testcase #2131.446 ms4 MB + 184 KBAcceptedScore: 4

Testcase #2231.295 ms4 MB + 188 KBAcceptedScore: 4

Testcase #231 s58 MB + 600 KBTime Limit ExceededScore: 0

Testcase #241 s52 MB + 648 KBTime Limit ExceededScore: 0

Testcase #251 s46 MB + 872 KBTime Limit ExceededScore: 0


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