oj.uz

Submission #25071

# Submission time Handle Problem Language Result Execution time Memory
25071 2017-06-20T05:54:43 Z zigui Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 26 ms 3960 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;

bool make_cycle(int x, int a, int b){
	int dist[MX] = {}, prv[MX] = {};
	dist[x] = 100;
	queue<int> Q; Q.push(a); dist[a] = 1;
	while(Q.size()){
		int p = Q.front(); Q.pop();
		for(int c : G[p]){
			if( dist[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){
	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);
			}
		}
	}
	return false;
}

int main()
{
	int N, M;
	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] = {};
		vector<int> L;
		uf.clear();
		
		for(int c : G[i]) L.push_back(c), chk[c] = 1;
		chk[i] = 1;
		for(int j = 1; j <= N; j++){
			if( chk[j] == 0 ){
				for(int c : G[j] ) uf.merge(j, c);
			}
		}
		vector<int> group[MX];
		for(int j = 1; j <= N; j++){
			if( chk[j] ) group[uf.find(j)].push_back(j);
		}
		for(int j = 1; j <= N; j++){
			if( check(i, group[j]) ) return 0;
		}
	}
	printf("no\n");
}

Compilation message

indcyc.cpp: In function 'bool check(int, std::vector<int>&)':
indcyc.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++){
                   ^
indcyc.cpp:73: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:86: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:88: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 3036 KB Output is correct
2 Correct 0 ms 3036 KB Output is correct
3 Correct 0 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct
5 Correct 0 ms 3036 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3036 KB Wrong adjacency

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3036 KB Output is correct
2 Incorrect 0 ms 3036 KB Wrong answer on graph without induced cycle

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3036 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3168 KB Output is correct
2 Incorrect 0 ms 3168 KB Wrong adjacency
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3036 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3564 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3300 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3960 KB Wrong adjacency
2 Halted 0 ms 0 KB -