oj.uz

Submission #244331

# Submission time Handle Problem Language Result Execution time Memory
244331 2020-07-03T15:59:30 Z hihi Potemkin cycle (CEOI15_indcyc) C++
100 / 100
 406 ms 95224 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6528 KB Output is correct
2 Correct 10 ms 5760 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6656 KB Output is correct
2 Correct 12 ms 7424 KB Output is correct
3 Correct 19 ms 9344 KB Output is correct
4 Correct 18 ms 8576 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8576 KB Output is correct
2 Correct 14 ms 7936 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 26344 KB Output is correct
2 Correct 39 ms 13432 KB Output is correct
3 Correct 125 ms 25900 KB Output is correct
4 Correct 39 ms 12924 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 54904 KB Output is correct
2 Correct 159 ms 58360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 10616 KB Output is correct
2 Correct 125 ms 10744 KB Output is correct
3 Correct 406 ms 95224 KB Output is correct
4 Correct 343 ms 94840 KB Output is correct