Submission #136271

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136271	2019-07-25T05:20:33 Z	윤교준(#3260)	Link (CEOI06_link)	C++14	0 / 100	1500 ms	20308 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	4344 KB	Output isn't correct
2	Incorrect	6 ms	4344 KB	Output isn't correct
3	Incorrect	6 ms	4344 KB	Output isn't correct
4	Incorrect	11 ms	4444 KB	Output isn't correct
5	Incorrect	15 ms	4472 KB	Output isn't correct
6	Incorrect	350 ms	5344 KB	Output isn't correct
7	Incorrect	346 ms	5688 KB	Output isn't correct
8	Execution timed out	1530 ms	6264 KB	Time limit exceeded
9	Execution timed out	1538 ms	7996 KB	Time limit exceeded
10	Incorrect	926 ms	7704 KB	Output isn't correct
11	Execution timed out	1522 ms	14060 KB	Time limit exceeded
12	Execution timed out	1591 ms	8828 KB	Time limit exceeded
13	Execution timed out	1534 ms	12204 KB	Time limit exceeded
14	Execution timed out	1543 ms	13056 KB	Time limit exceeded
15	Execution timed out	1569 ms	16084 KB	Time limit exceeded
16	Execution timed out	1589 ms	17508 KB	Time limit exceeded
17	Execution timed out	1584 ms	18428 KB	Time limit exceeded
18	Execution timed out	1581 ms	17356 KB	Time limit exceeded
19	Execution timed out	1577 ms	18112 KB	Time limit exceeded
20	Execution timed out	1588 ms	18236 KB	Time limit exceeded
21	Execution timed out	1577 ms	19584 KB	Time limit exceeded
22	Execution timed out	1590 ms	19644 KB	Time limit exceeded
23	Execution timed out	1590 ms	18868 KB	Time limit exceeded
24	Execution timed out	1592 ms	20000 KB	Time limit exceeded
25	Execution timed out	1586 ms	20308 KB	Time limit exceeded