oj.uz

Submission #54890

# Submission time Handle Problem Language Result Execution time Memory
54890 2018-07-05T08:58:45 Z 윤교준(#1510) Potemkin cycle (CEOI15_indcyc) C++11
100 / 100
 456 ms 5592 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }

const int MAXN = 1005;
const int MAXM = 100005;

vector<int> G[MAXN];

int isS[MAXN][MAXN], isSn;

bitset<MAXN> C[MAXN];

int E[MAXN], En;

int D[MAXN];
int chk[MAXN], chkn;

int O[MAXN];
int A[MAXM], B[MAXM];

int N, M;

void answer(int i, int a, int b, int en) {
	chkn++;

	queue<int> PQ;
	chk[a] = chkn; PQ.push(a);

	bool isf = false;

	for(int idx; !PQ.empty(); PQ.pop()) {
		idx = PQ.front();

		for(int v : G[idx]) {
			if(v == i || v == a || chk[v] == chkn) continue;
			if(C[i][v] && C[i][idx]) continue;
			if(v != b && E[v] != en) continue;

			chk[v] = chkn;
			D[v] = idx;
			PQ.push(v);

			if(v == b) {
				isf = true;
				break;
			}
		}

		if(isf) break;
	}

	for(int i = b; i != a; i = D[i]) printf("%d ", i);
	printf("%d %d\n", a, i);
	exit(0);
}

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		fg(G, A[i], B[i]);
		C[A[i]][B[i]] = C[B[i]][A[i]] = true;
	}

	for(int i = 1; i <= N; i++) {
		int dg = sz(G[i]);
		chkn++; isSn++;
		
		En = 0;
		fill(E, E+N+1, 0);
		
		for(int j = 1; j <= N; j++) {
			if(j == i || C[i][j]) continue;
			if(chk[j] == chkn) continue;
			
			En++;
			queue<int> PQ;
			chk[j] = chkn; PQ.push(j);
			
			for(int idx; !PQ.empty(); PQ.pop()) {
				idx = PQ.front();
				E[idx] = En;
				
				for(int v : G[idx]) {
					if(chk[v] == chkn) continue;
					if(C[i][v]) {
						isS[v][En] = isSn;
						continue;
					}
					chk[v] = chkn;
					PQ.push(v);
				}
			}
		}
		
		for(int ji = 0; ji < dg; ji++) for(int ki = ji+1; ki < dg; ki++) {
			int j = G[i][ji], k = G[i][ki];
			if(C[j][k]) continue;
			
			for(int e = 1; e <= En; e++) {
				if(isS[j][e] != isSn || isS[k][e] != isSn) continue;
				answer(i, j, k, e);
			}
		}
	}

	puts("no");
	return 0;
}

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 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 4 ms 804 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1828 KB Output is correct
2 Correct 3 ms 1828 KB Output is correct
3 Correct 4 ms 1828 KB Output is correct
4 Correct 13 ms 1876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1876 KB Output is correct
2 Correct 22 ms 1876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3556 KB Output is correct
2 Correct 12 ms 3556 KB Output is correct
3 Correct 218 ms 5440 KB Output is correct
4 Correct 151 ms 5440 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5440 KB Output is correct
2 Correct 456 ms 5440 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5440 KB Output is correct
2 Correct 126 ms 5440 KB Output is correct
3 Correct 37 ms 5440 KB Output is correct
4 Correct 447 ms 5592 KB Output is correct