oj.uz

Submission #25097

# Submission time Handle Problem Language Result Execution time Memory
25097 2017-06-20T06:48:27 Z zigui Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 549 ms 7912 KB 
#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 1005;
const int MM = 1000000007;

vector<int> G[MX];
bool H[MX][MX];

int a, b;

struct UF{
	int t[MX];
	int find(int x){
		return t[x] ? t[x] = find(t[x]) : x;
	}
	int merge(int a, int b){
		a = find(a), b = find(b);
		return a == b ? 0 : (t[a] = b, 1);
	}
	void clear(){
		memset(t, 0, sizeof(t));
	}
} uf;

int N, M;

bool make_cycle(int x, int a, int b, bool chk[MX]){
	int dist[MX] = {}, prv[MX] = {};
	queue<int> Q; Q.push(a); dist[a] = 1;
	chk[b] = 0;
	while(Q.size()){
		int p = Q.front(); Q.pop();
		for(int c : G[p]){
			if( dist[c] || chk[c]) continue;
			dist[c] = dist[p] + 1; prv[c] = p;
			Q.push(c);
		}
	}
	vector<int> L;
	L.push_back(x);
	L.push_back(b);
	while(b != a){
		b = prv[b];
		L.push_back(b);
	}
	for(int c : L) printf("%d ", c);
	printf("\n");
	return true;
}

bool check(int x, vector<int> &X, bool chk[MX]){
	for(int i = 0; i < X.size(); i++){
		for(int j = i+1; j < X.size(); j++){
			int &a = X[i], &b = X[j];
			if( !H[a][b] ){
				return make_cycle(x, a, b, chk);
			}
		}
	}
	return false;
}

int vst[MX][MX], t = 1;
int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++){
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
		H[a][b] = H[b][a] = 1;
	}
	for(int i = 1; i <= N; i++){
		bool chk[MX] = {};
		uf.clear();
		
		for(int c : G[i]) chk[c] = 1;
		chk[i] = 1;
		for(int j = 1; j <= N; j++){
			if( chk[j] == 0 ){
				for(int c : G[j] ) if( chk[c] == 0 ) uf.merge(j, c);
			}
		}
		vector<int> group[MX];
		t++;
		for(int j = 1; j <= N; j++){
			if( !chk[j] ) continue;
			for(int c : G[j]) if( !chk[c] && vst[uf.find(c)][j] != t ){
				group[uf.find(c)].push_back(j);
				vst[uf.find(c)][j] = t;
			}
		}
		for(int j = 1; j <= N; j++){
			if( group[j].size() && check(i, group[j], chk) ) return 0;
		}
	}
	printf("no\n");
}

Compilation message

indcyc.cpp: In function 'bool check(int, std::vector<int>&, bool*)':
indcyc.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                   ^
indcyc.cpp:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i+1; j < X.size(); j++){
                      ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
indcyc.cpp:90:24: 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 0 ms 6988 KB Output is correct
2 Correct 0 ms 6988 KB Output is correct
3 Correct 0 ms 6988 KB Output is correct
4 Correct 0 ms 6988 KB Output is correct
5 Correct 0 ms 6988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6988 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6988 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7120 KB Output is correct
2 Correct 0 ms 7120 KB Output is correct
3 Correct 0 ms 7120 KB Output is correct
4 Correct 19 ms 7120 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7516 KB Output is correct
2 Correct 9 ms 7384 KB Output is correct
3 Correct 419 ms 7516 KB Output is correct
4 Correct 209 ms 7384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7252 KB Output is correct
2 Correct 366 ms 7252 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7912 KB Output is correct
2 Correct 103 ms 7912 KB Output is correct
3 Correct 36 ms 7780 KB Output is correct
4 Correct 549 ms 7780 KB Output is correct