提交记录 7866


用户 题目 状态 得分 用时 内存 语言 代码长度
mengbier noip18d. 【NOIP2018】旅行 Accepted 100 8.573 ms 460 KB C++ 1.62 KB
提交时间 评测时间
2019-01-25 19:08:20 2020-08-01 01:09:27
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn=5e3+3;
struct Edge{
	int x,y;
	bool operator <(const Edge&a)const{
		if(x!=a.x)return x<a.x;
		return y<a.y;
	}
}c[maxn<<1];
struct Road{
	int to;
	int last;
}a[maxn<<1];
int n;
int m;
int T;
int mm;
int s,t;
int cnt;
int tot;
int haha;
bool flag;
int ans[maxn];
int vis[maxn];
int head[maxn];
int temp[maxn];
bool HA();
void I(int&);
void HAHA(int);
void HA(int,int);
int main(){
	I(n),I(m);
	for(int i=1,x,y;i<=m;++i)
		I(c[mm].x),I(c[mm].y),++mm,
		c[mm].x=c[mm-1].y,c[mm].y=c[mm-1].x,++mm;
	std::sort(c,c+mm);
	for(int i=mm-1;~i;--i)
		HA(c[i].x,c[i].y);
	if(m==n-1){
		T=1,HAHA(1);
		for(int i=1;i<n;++i)
			printf("%d ",temp[i]);
		printf("%d\n",temp[n]);
		return 0;
	}
	for(int i=1;i<=tot;++i){
		s=c[i].x,t=c[i].y;
		cnt=0,++T,haha=0,HAHA(1);
		if(cnt==n && (!flag || HA()))
			memcpy(ans,temp,sizeof(ans)),flag=true;
	}
	for(int i=1;i<n;++i)
		printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
	return 0;
}
inline void HA(int x,int y){
	a[++tot].to=y;
	a[tot].last=head[x];
	head[x]=tot;
}
inline void I(int&x){
	register char ch;
	while(ch=getchar(),ch<'/');x=ch-'0';
	while(ch=getchar(),ch>'/')x=((x+(x<<2))<<1)+ch-'0';
}
inline bool HA(){
	for(int i=1;i<=n;++i)
		if(ans[i]!=temp[i])
			return temp[i]<ans[i];
	return false;
}
#define y a[i].to
inline void HAHA(int x){
	if(haha==-1)return;
	vis[x]=T,temp[++cnt]=x;
	if(flag && !haha && temp[cnt]>ans[cnt])
		return haha=-1,void();
	if(flag && temp[cnt]<ans[cnt])haha=1;
	for(int i=head[x];i;i=a[i].last){
		if(vis[y]==T)continue;
		if(x==s && y==t)continue;
		if(x==t && y==s)continue;
		HAHA(y);
	}
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #139.62 us60 KBAcceptedScore: 4

Testcase #244.48 us60 KBAcceptedScore: 4

Testcase #345.84 us60 KBAcceptedScore: 4

Testcase #460.37 us64 KBAcceptedScore: 4

Testcase #560.96 us64 KBAcceptedScore: 4

Testcase #6297.09 us136 KBAcceptedScore: 4

Testcase #7296.98 us140 KBAcceptedScore: 4

Testcase #8295.94 us144 KBAcceptedScore: 4

Testcase #9304.62 us128 KBAcceptedScore: 4

Testcase #10301.22 us124 KBAcceptedScore: 4

Testcase #111.498 ms380 KBAcceptedScore: 4

Testcase #121.507 ms420 KBAcceptedScore: 4

Testcase #131.498 ms432 KBAcceptedScore: 4

Testcase #141.497 ms380 KBAcceptedScore: 4

Testcase #151.491 ms460 KBAcceptedScore: 4

Testcase #1645.3 us80 KBAcceptedScore: 4

Testcase #1744.17 us80 KBAcceptedScore: 4

Testcase #1896.86 us84 KBAcceptedScore: 4

Testcase #19114.61 us84 KBAcceptedScore: 4

Testcase #20627.4 us168 KBAcceptedScore: 4

Testcase #21407.65 us168 KBAcceptedScore: 4

Testcase #228.573 ms168 KBAcceptedScore: 4

Testcase #235.722 ms456 KBAcceptedScore: 4

Testcase #243.972 ms444 KBAcceptedScore: 4

Testcase #254.593 ms432 KBAcceptedScore: 4


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