oj.uz

Submission #46860

# Submission time Handle Problem Language Result Execution time Memory
46860 2018-04-24T04:26:02 Z HachikujiMayoi Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 192 ms 6880 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1007;

int n, m;
int blocked[N], par[N], vis[N];
vector <int> g[N], comp[N];
int G[N][N];

int Get(int a){
	if(par[a] == a) return a;
	return par[a] = Get(par[a]);
}

void Union(int a, int b){
	a = Get(a);
	b = Get(b);
	if(a == b) return;
	if(comp[b].size() > comp[a].size()) swap(a, b);
	par[b] = a;
	for(auto i : comp[b]) comp[a].push_back(i);
}

void dfs(int at){
	vis[at] = 1;
	if(blocked[at]) return;
	for(auto i : g[at]){
		if(!vis[i]){
			Union(at, i);
			dfs(i);
		}
	}
}

void solve(int a, int b, int c){
	blocked[a] = 0;
	blocked[c] = 0;
	vector <int> dis(n + 1, N), dad(n + 1, 0);
	queue <int> q;
	dis[a] = 0;
	q.push(a);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto i : g[u]){
			if(blocked[i]) continue;
			if(dis[i] > dis[u] + 1){
				dis[i] = dis[u] + 1;
				dad[i] = u;
				q.push(i);
			}
		}
	}
	printf("%d %d %d", a, b, c);
	int cur = dad[c];
	while(cur != a){
		printf(" %d", cur);		
		cur = dad[cur];
	}
	printf("\n");
}

int main(){
	int x, y;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
		G[x][y] = 1;
		G[y][x] = 1;
	}
	for(int i = 1; i <= n; ++i) G[i][i] = 1;
	for(int i = 1; i <= n; ++i){
		memset(blocked, 0, sizeof(blocked));
		memset(vis, 0, sizeof(vis));
		blocked[i] = 1;
		for(auto j : g[i]){
			blocked[j] = 1;
		}
		for(int j = 1; j <= n; ++j){
			if(blocked[j]) comp[j] = {j};
			else comp[j] = {};
			par[j] = j;
		}
		for(int j = 1; j <= n; ++j){
			if(!vis[j]) dfs(j);
		}
		for(int j : g[i]){
			int k = Get(j);
			for(auto o : comp[k]){
				if(!G[j][o]){
					solve(j, i, o);
					return 0;
				}
			}
		}
	}
	printf("no\n");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:67: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 532 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 820 KB Output is correct
2 Correct 2 ms 820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 996 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 996 KB Output is correct
2 Correct 3 ms 1004 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1900 KB Output is correct
2 Correct 5 ms 1900 KB Output is correct
3 Correct 5 ms 1900 KB Output is correct
4 Correct 11 ms 1988 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1988 KB Output is correct
2 Correct 8 ms 1988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5216 KB Output is correct
2 Correct 24 ms 5344 KB Output is correct
3 Correct 185 ms 5988 KB Output is correct
4 Correct 116 ms 5988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5988 KB Output is correct
2 Correct 92 ms 5988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5988 KB Output is correct
2 Correct 29 ms 5988 KB Output is correct
3 Correct 29 ms 6356 KB Output is correct
4 Correct 192 ms 6880 KB Output is correct