提交记录 12891


用户 题目 状态 得分 用时 内存 语言 代码长度
Sunward 2002. 【NOIP2018】旅行(加强版) Accepted 100 262.143 ms 353 MB + 780 KB C++ 3.15 KB
提交时间 评测时间
2020-06-24 18:00:37 2020-06-24 18:00:54
#include<bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(register int i = l;i <= r; ++ i)
using namespace std;
inline int read()
{
	register char cc = getchar(); register int cn(0), flus(1);
	while(cc > '9' || cc < '0') {if(cc == '-') flus = -flus; cc = getchar();}
	while(cc >= '0' && cc <= '9') {cn = cn * 10 + cc - 48; cc = getchar();}
	return cn * flus;
}
const int N = 1000010;
struct edge
{
	int to, next;
	bool del;
} e[N << 1];
int tot, head[N];
int n, m;
bool vis[N];
bool flag;
bool cir[N];
int point_in(1);
bool del = 0;
inline void add(int u, int v)
{
	e[++tot].next = head[u];
	head[u] = tot;
	e[tot].to = v;
	e[++tot].next = head[v];
	head[v] = tot;
	e[tot].to = u;
	return ;
}
//priority_queue<int> que;
void dfs(int u, int last)
{
	printf("%d ",u);
	priority_queue<int, deque<int>, greater<int> > que;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last || e[i].del) continue;
		//dfs(v, u);
		que.push(v);
	}
	while(!que.empty())
	{
		int v = que.top();
		que.pop();
		dfs(v, u);
	}
}
void dfs1(int u, int last)
{
	vis[u] = 1;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last || e[i].del) continue;
		if(vis[v])
		{
			flag = 1;
			cir[v] = 1;
			cir[u] = 1;
			return ;
		}
		dfs1(v, u);
		if(cir[v] && flag)
		{
			if(cir[u]) flag = 0;
			cir[u] = 1;
			return ;
		}
	}
}
void dfs2(int u, int last)
{
	// printf("dfs2 %d \n",u);
	vis[u] = 1;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		// printf("v = %d \n",v);
		if(v == last) continue;
		if(cir[v])
		{
			point_in = v;
			return ;
		}
	}
}
int back(int u, int last)
{
	// printf("back %d %d \n",u,last);
	// priority_queue<int, deque<int>, greater<int> > q;
	int _min(1e9);
	int nxt;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		// printf("v = %d \n",v);
		if(v == last) continue;
		if(!vis[v]) _min = min(_min, v);
		if(cir[v]) nxt = v;
	}
	// printf("_min = %d \n",_min);
	if(_min != 1e9)
	{
		return _min;
	}
	return back(nxt, u);
}
void dfs4(int u, int last)
{
	printf("");
//	printf("dfs4 %d %d \n",u,last);
	vis[u] = 1;
	priority_queue<int, deque<int>, greater<int> > q;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last) continue;
		q.push(v);
	}
	bool first(0);
	while(!q.empty())
	{
		if(del) return ;
		int v = q.top();
		q.pop();
		if(cir[v] && q.empty())
		{
			if(back(u, v) < v)
			{
				// printf("back(%d,%d) = %d \n",u,v,back(u, v));
				for(register int i = head[u]; i; i = e[i].next)
				{
					int v1 = e[i].to;
					if(v1 == v)
					{
						e[i].del = 1;
						if(e[i + 1].to == u) e[i + 1].del = 1;
						else if(e[i - 1].to == u) e[i - 1].del = 1;
					}
				}
				del = 1;
				return ;
			}
		}
		dfs4(v, u);
	}
	return ;
}
signed main()
{
	// printf("fuck \n");
//	freopen("in.txt","r",stdin);
	n = read(), m = read();
	rep(i, 1, m)
	{
		int u, v;
		u = read(), v = read();
		add(u, v);
	}
	if(n == m + 1)
	{
		dfs(1, 0);
		return 0;
	}
	dfs1(1, 0);
	memset(vis, 0, sizeof(vis));
	if(!cir[1]) dfs2(1, 0);
	// printf("point_in = %d \n",point_in);
	dfs4(point_in, 0);
	rep(i, 1, n)
	{
		// printf("cir[%d] = %d \n",i,cir[i]);
	}
	dfs(1, 0);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #139.02 us60 KBAcceptedScore: 5

Testcase #2131.27 us1 MB + 20 KBAcceptedScore: 5

Testcase #356.88 us92 KBAcceptedScore: 5

Testcase #456.09 us100 KBAcceptedScore: 5

Testcase #51.279 ms2 MB + 104 KBAcceptedScore: 5

Testcase #61.271 ms1 MB + 932 KBAcceptedScore: 5

Testcase #730.996 ms36 MB + 60 KBAcceptedScore: 5

Testcase #831.33 ms24 MB + 184 KBAcceptedScore: 5

Testcase #9204.054 ms182 MB + 996 KBAcceptedScore: 5

Testcase #10206.799 ms213 MB + 992 KBAcceptedScore: 5

Testcase #11203.63 ms123 MB + 1012 KBAcceptedScore: 5

Testcase #12205.248 ms157 MB + 460 KBAcceptedScore: 5

Testcase #131.511 ms3 MB + 172 KBAcceptedScore: 5

Testcase #141.485 ms3 MB + 796 KBAcceptedScore: 5

Testcase #1534.028 ms43 MB + 872 KBAcceptedScore: 5

Testcase #1634.677 ms50 MB + 680 KBAcceptedScore: 5

Testcase #17261.331 ms353 MB + 780 KBAcceptedScore: 5

Testcase #18262.143 ms353 MB + 760 KBAcceptedScore: 5

Testcase #19244.981 ms192 MB + 924 KBAcceptedScore: 5

Testcase #20257.122 ms282 MB + 604 KBAcceptedScore: 5


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