Submission #244331

#	Time	Username	Problem	Language	Result	Execution time	Memory
244331		hihi	Potemkin cycle (CEOI15_indcyc)	C++98	100 / 100	406 ms	95224 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
int n,m,from[200005],to[200005],cur,a,b;
vector<int> edge[1005];
vector<int> adj[200005];
int con[1005][1005];
void addedge(int a,int b) {
	con[a][b]=con[b][a]=1;
	from[cur]=a;
	to[cur]=b;
	edge[a].pb(cur++);
	from[cur]=b;
	to[cur]=a;
	edge[b].pb(cur++);
}
int p[200005],vis[200005],node=-1;
void dfs(int v) {
	if (node!=-1) return;
	vis[v]=1;
	for (int x:adj[v]) {
		if (vis[x]==1) {
			node=v;
			return;
		}
		if (vis[x]==0) dfs(x);
	}
	vis[v]=2;
}
queue<int> q;
vector<int> ans,e;
void bfs(int s) {
	q.push(s);
	memset(vis,0,sizeof(vis));
	p[s]=-1;
	vis[s]=1;
	while(!q.empty()) {
		int v=q.front();
		q.pop();
		for (int x:adj[v]) {
			if (x==s) {
				int c=v;
				while(c!=x) {
					e.pb(c);
					c=p[c];
				}
				e.pb(x);
				if (from[e[1]]==to[e[0]] || to[e[1]]==to[e[0]]) ans.pb(to[e[0]]);
				else ans.pb(from[e[0]]);
				for (int i=1;i<sz(e);i++) {
					if (ans.back()==from[e[i]]) ans.pb(to[e[i]]);
					else if (ans.back()==to[e[i]]) ans.pb(from[e[i]]);
					else assert(0);
				}
				return;
			}
			if (!vis[x]) {
				vis[x]=1;
				p[x]=v;
				q.push(x);
			}
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++) {
		scanf("%d%d",&a,&b);
		--a,--b;
		addedge(a,b);
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<sz(edge[i]);j++) {
			for (int k=j+1;k<sz(edge[i]);k++) {
				if (!con[to[edge[i][j]]][to[edge[i][k]]]) {
					adj[edge[i][j]^1].pb(edge[i][k]);
					adj[edge[i][k]^1].pb(edge[i][j]);
				}
			}
		}
	}
	for (int i=0;i<cur;i++) {
		if (!vis[i]) p[i]=-1,dfs(i);
		if (node!=-1) break;
	}
	if (node==-1) printf("no\n");
	else {
		bfs(node);
		for (int i=0;i<sz(ans);i++) {
			printf("%d%c", ans[i]+1,(i<sz(ans)-1)?' ':'\n');
		}
	}
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
indcyc.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10