oj.uz

Submission #95125

# Submission time Handle Problem Language Result Execution time Memory
95125 2019-01-27T14:24:41 Z ekrem Potemkin cycle (CEOI15_indcyc) C++
100 / 100
 264 ms 5368 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1005
#define M 100005
using namespace std;

typedef pair < int , int > ii;

int n, m, r, grp, h[N], vis[N], u[N][N], uu[N], a[N][N], par[N];
vector < int > g[N];
queue < ii > q;

void dfs(int node){
	h[node] = grp;
	if(uu[node])
		return;
	for(int i = 0; i < g[node].size(); i++)
		if(!h[g[node][i]])
			dfs(g[node][i]);
}

void sp(int uuu, int v){
	// cout << "AMK" << uuu << " " << v << endl;

	vis[r] = 1;
	for(int i = 0; i < g[r].size(); i++)
		vis[g[r][i]] = 1;
	vis[v] = 0;

	q.push(mp(uuu, r));
	while(!q.empty()){
		int node = q.front().st;
		int pr = q.front().nd;
		q.pop();
		// cout << pr << " " << node << endl;

		par[node] = pr;

		if(node == v){
			while(node != 0){
				printf("%d ", node);
				node = par[node];
			}
			exit(0);
		}

		for(int i = 0; i < g[node].size(); i++)
			if(!vis[g[node][i]]){
				vis[g[node][i]] = 1;
				q.push(mp(g[node][i], node));
			}
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		a[u][v] = a[v][u] = 1;
		g[u].pb(v);
		g[v].pb(u);
	}

	for(r = 1; r <= n; r++){

		memset(h, 0, sizeof h);
		memset(uu, 0, sizeof uu);

		int sz = g[r].size();
		uu[r] = 1;
		for(int i = 0; i < sz; i++)
			uu[g[r][i]] = 1;


		// for(int i = 0; i < sz; i++)
		// 	for(int j = i + 1; j < sz; j++)
		// 		u[g[r][i]][g[r][j]] = u[g[r][j]][g[r][i]] = r;

		grp = 1;
		for(int i = 1; i <= n; i++)
			if(!h[i]){
				dfs(i);
				grp++;
			}

		// for(int i = 1; i <= n; i++)
		// 	cout << i << " " << h[i] << endl;

		for(int i = 0; i < sz; i++)
			for(int j = i + 1; j < sz; j++)
				if(!a[g[r][i]][g[r][j]] and h[g[r][i]] == h[g[r][j]])
					sp(g[r][i], g[r][j]);

	}
	puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'void sp(int, int)':
indcyc.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[r].size(); i++)
                 ~~^~~~~~~~~~~~~
indcyc.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[node].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:61: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u ,&v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1660 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 4 ms 1656 KB Output is correct
4 Correct 16 ms 1656 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5004 KB Output is correct
2 Correct 14 ms 4792 KB Output is correct
3 Correct 231 ms 5116 KB Output is correct
4 Correct 107 ms 4728 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4756 KB Output is correct
2 Correct 92 ms 4856 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3292 KB Output is correct
2 Correct 94 ms 3284 KB Output is correct
3 Correct 27 ms 5240 KB Output is correct
4 Correct 264 ms 5368 KB Output is correct