Submission #136274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136274	2019-07-25T05:21:59 Z	윤교준(#3260)	Link (CEOI06_link)	C++14	28 / 100	432 ms	20440 KB

link

#include <bits/stdc++.h>
#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(debug) printf("Color %d\n", i);
		if(isC[i]) goCycle(i, 1 == i ? K : K-1);
		else goTree(i, 1 == i ? K : K-1);
		Ans++;
	}

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

Subtask #1

28.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4344 KB	Output is correct
2	Incorrect	6 ms	4344 KB	Output isn't correct
3	Incorrect	6 ms	4344 KB	Output isn't correct
4	Correct	7 ms	4472 KB	Output is correct
5	Incorrect	8 ms	4472 KB	Output isn't correct
6	Incorrect	20 ms	5240 KB	Output isn't correct
7	Incorrect	31 ms	5628 KB	Output isn't correct
8	Incorrect	42 ms	6264 KB	Output isn't correct
9	Correct	64 ms	8148 KB	Output is correct
10	Incorrect	62 ms	7648 KB	Output isn't correct
11	Correct	107 ms	14224 KB	Output is correct
12	Incorrect	126 ms	8952 KB	Output isn't correct
13	Correct	176 ms	12252 KB	Output is correct
14	Incorrect	207 ms	13104 KB	Output isn't correct
15	Incorrect	280 ms	16176 KB	Output isn't correct
16	Incorrect	277 ms	17560 KB	Output isn't correct
17	Incorrect	397 ms	18552 KB	Output isn't correct
18	Incorrect	365 ms	17416 KB	Output isn't correct
19	Incorrect	371 ms	18176 KB	Output isn't correct
20	Incorrect	407 ms	18304 KB	Output isn't correct
21	Incorrect	401 ms	19536 KB	Output isn't correct
22	Correct	419 ms	19648 KB	Output is correct
23	Correct	381 ms	19036 KB	Output is correct
24	Incorrect	432 ms	20152 KB	Output isn't correct
25	Incorrect	425 ms	20440 KB	Output isn't correct