oj.uz

답안 #136287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136287 2019-07-25T05:41:29 Z 윤교준(#3260) Link (CEOI06_link) C++14
0 / 100
 421 ms 35476 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 sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
void fuk() { puts("ERR!"); exit(-1); }

const bool debug = 0;

const int MAXN = 500055;

struct DJF {
	DJF() { init(); }
	int ud[MAXN];

	void init() { iota(ud, ud+MAXN, 0); }
	int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void uf(int a, int b) { ud[uf(b)] = uf(a); }
} djf, djfC;

vector<vector<int>> CV;
int CI[MAXN], CJ[MAXN], CL[MAXN], Cn;
bitset<MAXN> isC;

int dep[MAXN];

int A[MAXN], O[MAXN];
bitset<MAXN> ison, isdead, chk;

int N, K, Ans;

int getDC(int a, int b) { return CJ[a] <= CJ[b] ? CJ[b]-CJ[a] : CL[CI[a]] - (CJ[a]-CJ[b]); }
void goCycle(int v, int l) {
	for(int i = v;;) {
		i = djfC.uf(i);
		if(chk[i] || getDC(v, i) > l) break;
		chk[i] = true;
		djfC.uf(A[i], i);
	}
}

void goTree(int v, int l) {
	int i = v;
	for(;;) {
		i = djf.uf(i);
		if(isC[i]) break;
		if(dep[v] - dep[i] > l) break;
		chk[i] = true;
		djf.uf(A[i], i);
	}
	if(isC[i] && dep[v] - dep[i] <= l)
		goCycle(i, l - (dep[v] - dep[i]));
}

void dfs(int i) {
	isdead[i] = true;
	if(!isC[A[i]] && !isdead[A[i]]) dfs(A[i]);
	dep[i] = dep[A[i]] + 1;
	CI[i] = CI[A[i]];
}

int predfs(vector<int> &V, int i) {
	ison[i] = true; V.eb(i);
	if(isdead[A[i]]) return 0;
	if(ison[A[i]]) return A[i];
	int ret = predfs(V, A[i]);
	isdead[i] = true;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K;
	for(int i = 0, a, b; i < N; i++) {
		cin >> a >> b;
		A[a] = b;
	}
	for(int i = 1; i <= N; i++) if(!A[i]) fuk();

	for(int i = 1, v; i <= N; i++) if(!isdead[i]) {
		vector<int> V;
		v = predfs(V, i);
		if(!v) continue;
		V.erase(V.begin(), find(allv(V), v));
		CV.eb(V);
		for(int j = 0, n = sz(V), v; j < n; j++) {
			v = V[j];
			isC[v] = true;
			CI[v] = Cn;
			CJ[v] = j;
		}
		CL[Cn] = sz(V);
		Cn++;
	}

	isdead.reset();
	for(int i = 1; i <= N; i++) if(!isC[i] && !isdead[i]) dfs(i);

	if(debug) {
	for(int i = 1; i <= N; i++)
		printf("%d ; %d / %d %d | %d\n", i, int(isC[i]), CI[i], CJ[i], dep[i]);
	for(int i = 0; i < Cn; i++) printf("Cy %d ; %d\n", i, CL[i]);
	}

	iota(O, O+N+1, 0); sort(O+2, O+N+1, [&](int a, int b) -> bool {
		if(isC[a] != isC[b]) return isC[b];
		if(!isC[a]) return dep[a] > dep[b];
		if(CI[a] != CI[b]) return CI[a] < CI[b];
		return CJ[a] < CJ[b];
	});
	
	for(int oi = 1, i; oi <= N; oi++) {
		i = O[oi];
		if(chk[i]) continue;
		if(1 != i && isC[i]) continue;
		if(isC[i]) goCycle(i, 1 == i ? K : K-1);
		else goTree(i, 1 == i ? K : K-1);
		if(debug) printf("Color %d\n", i);
		Ans++;
	}

	for(int i = 0; i < Cn; i++) {
		vector<bool> V;
		for(int v : CV[i]) V.pb(chk[v]);
		for(int v : CV[i]) V.pb(chk[v]);

		int l = CL[i]<<1;
		vector<vector<int>> nxt(20, vector<int>(l|1, l));
		for(int i = l; i--;) {
			if(V[i]) {
				nxt[0][i] = nxt[0][i+1];
			} else {
				nxt[0][i] = i;
			}
		}
		for(int i = 0, j; i < l; i++) {
			if(V[i]) continue;
			j = i+K-1;
			if(l <= j) nxt[0][i] = l;
			else nxt[0][i] = nxt[0][j+1];
		}
		for(int i = l; i--;) if(V[i]) nxt[0][i] = nxt[0][i+1];

		for(int j = 1; j < 20; j++) for(int i = 0; i < l; i++)
			nxt[j][i] = nxt[j-1][nxt[j-1][i]];

		if(debug) {
			printf("%d Cycle : l=%d : ", i, l);
			for(int v : CV[i]) printf("%d ", v); puts("");
			for(int j = 0; j < l; j++) printf("%d", int(V[j])); puts("");
			for(int j = 0; j < l; j++) printf("%d ", nxt[0][j]); puts("");
		}

		int ret = N+5;
		for(int k = 0; k < CL[i]; k++) if(!V[k]) {
			int t = 0, x = k;
			for(int j = 20, y; j--;) {
				y = nxt[j][x];
				if(k+CL[k] < y) continue;
				else {
					t |= 1<<j;
					x = y;
				}
			}
			t++;
			if(t < ret) ret = t;
		}

		if(N+5 <= ret) ret = 0;
		
		if(debug) {
			printf("C %d ; %d\n", i, ret);
		}

		Ans += ret;
	}

	cout << Ans-1 << endl;
	return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:155:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for(int v : CV[i]) printf("%d ", v); puts("");
    ^~~
link.cpp:155:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(int v : CV[i]) printf("%d ", v); puts("");
                                         ^~~~
link.cpp:156:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for(int j = 0; j < l; j++) printf("%d", int(V[j])); puts("");
    ^~~
link.cpp:156:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(int j = 0; j < l; j++) printf("%d", int(V[j])); puts("");
                                                        ^~~~
link.cpp:157:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for(int j = 0; j < l; j++) printf("%d ", nxt[0][j]); puts("");
    ^~~
link.cpp:157:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(int j = 0; j < l; j++) printf("%d ", nxt[0][j]); puts("");
                                                         ^~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4344 KB Output isn't correct
2 Incorrect 6 ms 4344 KB Output isn't correct
3 Incorrect 6 ms 4476 KB Output isn't correct
4 Incorrect 7 ms 4472 KB Output isn't correct
5 Incorrect 8 ms 4600 KB Output isn't correct
6 Incorrect 22 ms 6184 KB Output isn't correct
7 Incorrect 32 ms 6328 KB Output isn't correct
8 Incorrect 45 ms 7816 KB Output isn't correct
9 Incorrect 69 ms 13012 KB Output isn't correct
10 Incorrect 63 ms 11540 KB Output isn't correct
11 Incorrect 124 ms 35476 KB Output isn't correct
12 Incorrect 130 ms 9492 KB Output isn't correct
13 Incorrect 184 ms 20544 KB Output isn't correct
14 Incorrect 198 ms 21544 KB Output isn't correct
15 Incorrect 290 ms 29400 KB Output isn't correct
16 Incorrect 334 ms 34160 KB Output isn't correct
17 Incorrect 362 ms 31528 KB Output isn't correct
18 Incorrect 364 ms 25956 KB Output isn't correct
19 Incorrect 388 ms 28024 KB Output isn't correct
20 Incorrect 385 ms 28256 KB Output isn't correct
21 Incorrect 390 ms 32452 KB Output isn't correct
22 Incorrect 397 ms 32820 KB Output isn't correct
23 Incorrect 359 ms 32272 KB Output isn't correct
24 Incorrect 409 ms 33372 KB Output isn't correct
25 Incorrect 421 ms 33460 KB Output isn't correct