Submission #25075

#	Time	Username	Problem	Language	Result	Execution time	Memory
25075		zigui	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	846 ms	1048576 KiB

indcyc

#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, 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 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] && j != i) group[uf.find(j)].push_back(j);
		}
		for(int j = 1; j <= N; j++){
			if( check(i, group[j], chk) ) return 0;
		}
	}
	printf("no\n");
}

Compilation message (stderr)

indcyc.cpp: In function 'bool check(int, std::vector<int>&, bool*)':
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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10