提交记录 12858


用户 题目 状态 得分 用时 内存 语言 代码长度
luosiyuan noip18d. 【NOIP2018】旅行 Accepted 100 130.899 ms 848 KB C++11 1.95 KB
提交时间 评测时间
2020-06-13 19:44:46 2020-08-01 03:00:27
// 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;
char TTT;
vector<int> a;
vector<int> ans;
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);
	if(a>ans){
		TTT=1;
		return ;
	}
	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);
		if(TTT)return ;
	}
}
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 {
		ans.resize(n);
		for(int i=0;i<n;i++)ans[i]=n+1;
		for(int i=1;i<=n;i++){
			for(int j=h[i];j;j=e[j].next){
				if(usedb[j])continue;
				TTT=0;
				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=min(ans,a);
				//for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
				//cout<<endl;
				a.clear();
			}
		}
		for(int i=0;i<ans.size();i++)cout<<ans[i]<<' ';
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #141.1 us56 KBAcceptedScore: 4

Testcase #248.04 us56 KBAcceptedScore: 4

Testcase #340.46 us56 KBAcceptedScore: 4

Testcase #457.82 us64 KBAcceptedScore: 4

Testcase #564.77 us64 KBAcceptedScore: 4

Testcase #6210.34 us204 KBAcceptedScore: 4

Testcase #7210.67 us216 KBAcceptedScore: 4

Testcase #8212.82 us220 KBAcceptedScore: 4

Testcase #9229.09 us164 KBAcceptedScore: 4

Testcase #10229.62 us156 KBAcceptedScore: 4

Testcase #111.04 ms584 KBAcceptedScore: 4

Testcase #121.028 ms724 KBAcceptedScore: 4

Testcase #131.008 ms752 KBAcceptedScore: 4

Testcase #141.013 ms576 KBAcceptedScore: 4

Testcase #151.005 ms848 KBAcceptedScore: 4

Testcase #1647.96 us72 KBAcceptedScore: 4

Testcase #1747.27 us72 KBAcceptedScore: 4

Testcase #18218.72 us80 KBAcceptedScore: 4

Testcase #19277.43 us80 KBAcceptedScore: 4

Testcase #203.146 ms256 KBAcceptedScore: 4

Testcase #21671.49 us256 KBAcceptedScore: 4

Testcase #22106.878 ms256 KBAcceptedScore: 4

Testcase #23130.899 ms796 KBAcceptedScore: 4

Testcase #2468.674 ms764 KBAcceptedScore: 4

Testcase #2568.355 ms720 KBAcceptedScore: 4


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