Submission #136425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136425	2019-07-25T09:42:18 Z	onjo0127	Link (CEOI06_link)	C++11	100 / 100	610 ms	62216 KB

link

#include <bits/stdc++.h>
using namespace std;
#define sz(V) ((int)V.size())

const int _N = 500001, DBG = 0;
bool chk[_N];
int N, K, A[_N], vs[_N], dep[_N], rt[_N], rid[_N], ith[_N], p[20][_N], cs[20][_N], ans;
vector<vector<int> > R;
vector<int> S, G[_N];

void go(int x, int col) {
	S.push_back(x);
	vs[x] = col;
	if(vs[A[x]]) {
		if(vs[A[x]] == col) {
			vector<int> T;
			while(1) {
				int tmp = S.back(); S.pop_back();
				T.push_back(tmp);
				if(tmp == A[x]) break;
			}
			reverse(T.begin(), T.end());
			for(int i=0; i<T.size(); i++) rid[T[i]] = sz(R), ith[T[i]] = i+1;
			R.push_back(T);
		}
	}
	else go(A[x], col);
}

int mrk(int x, int k) {
	if(k <= 0) return x;
	chk[x] = 1;
	int d;
	if(ith[x]) {
		if(ith[x] < ith[A[x]]) d = ith[A[x]] - ith[x];
		else d = ith[A[x]] - ith[x] + sz(R[rid[x]]);
	}
	else if(ith[A[x]]) return A[x] = mrk(rt[x], k - dep[x]);
	else d = dep[x] - dep[A[x]];
	return A[x] = mrk(A[x], k - d);
}

void dfs(int RT, int x, int d) {
	// printf("dfs: x: %d, d: %d\n", x, d);
	dep[x] = d; rt[x] = RT;
	for(auto& it: G[x]) dfs(RT, it, d+1);
}

void showstat() {
	puts("Showing...");
	printf("answer: %d\n", ans);
	for(int i=1; i<=N; i++) printf("%d", chk[i]);
	puts("\n---------------------");
}

int main() {
	vector<int> Q;
	scanf("%d%d",&N,&K);
	for(int i=1; i<=N; i++) {
		int a, b; scanf("%d%d",&a,&b);
		A[a] = b;
	}
	for(int i=1; i<=N; i++) if(!vs[i]) go(i, i);
	for(int i=1; i<=N; i++) if(!ith[i]) {
		G[A[i]].push_back(i);
		Q.push_back(i);
	}
	for(int i=1; i<=N; i++) if(ith[i]) dfs(i, i, 0);
	chk[1] = 1;
	mrk(A[1], K);
	if(DBG) showstat();
	sort(Q.begin(), Q.end(), [&](int PP, int QQ) { return dep[PP] > dep[QQ]; });
	for(auto& it: Q) {
		if(chk[it]) continue;
		mrk(it, K); ++ans;
	}
	if(DBG) showstat();
	for(auto& it: R) {
		set<int> st;
		int M = sz(it);
		for(int j=0; j<M; j++) {
			p[0][j] = j; cs[0][j] = 0;
			if(!chk[it[j]]) st.insert(j);
		}
		if(st.empty()) continue;

		for(auto& jt: st) {
			if(jt <= M-K) {
				auto kt = st.lower_bound(jt + K);
				if(kt == st.end()) {
					p[0][jt] = *st.begin();
					cs[0][jt] = *st.begin() - jt + M;
				}
				else {
					p[0][jt] = *kt;
					cs[0][jt] = *kt - jt;
				}
			}
			else {
				auto kt = st.lower_bound(jt + K - M);
				if(kt == st.end()) p[0][jt] = jt, cs[0][jt] = M;
				else p[0][jt] = *kt, cs[0][jt] = *kt - jt + M;
			}
			// printf("next[%d]: %d, cost: %d\n", jt, p[0][jt], cs[0][jt]);
		}

		int L;
		for(int i=1; (1<<i)<=M; i++) {
			for(int j=0; j<M; j++) {
				p[i][j] = p[i-1][p[i-1][j]];
				cs[i][j] = cs[i-1][j] + cs[i-1][p[i-1][j]];
				cs[i][j] = min(cs[i][j], M);
			}
			L = i;
		}
		int mn = 1e9;
		for(auto& jt: st) {
			int sum = 0, now = jt, cnt = 0;
			for(int j=L; j>=0; j--) if(sum + cs[j][now] < M) {
				sum += cs[j][now], cnt += (1<<j), now = p[j][now];
				// printf("now: %d, sum: %d, cnt: %d\n", now, sum, cnt);
			}
			mn = min(mn, cnt + 1);
			// printf("jt: %d, cnt: %d\n", jt, cnt + 1);
		}
		ans += mn;
	}
	printf("%d", ans);
	return 0;
}

Compilation message

link.cpp: In function 'void go(int, int)':
link.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<T.size(); i++) rid[T[i]] = sz(R), ith[T[i]] = i+1;
                 ~^~~~~~~~~
link.cpp: In function 'int main()':
link.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&K);
  ~~~~~^~~~~~~~~~~~~~
link.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
link.cpp:120:43: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
     sum += cs[j][now], cnt += (1<<j), now = p[j][now];
                                       ~~~~^~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Correct	12 ms	12152 KB	Output is correct
3	Correct	13 ms	12280 KB	Output is correct
4	Correct	14 ms	12408 KB	Output is correct
5	Correct	15 ms	12536 KB	Output is correct
6	Correct	31 ms	14972 KB	Output is correct
7	Correct	43 ms	15860 KB	Output is correct
8	Correct	58 ms	18372 KB	Output is correct
9	Correct	90 ms	24980 KB	Output is correct
10	Correct	90 ms	23696 KB	Output is correct
11	Correct	167 ms	53424 KB	Output is correct
12	Correct	209 ms	23924 KB	Output is correct
13	Correct	228 ms	37820 KB	Output is correct
14	Correct	290 ms	42292 KB	Output is correct
15	Correct	348 ms	49324 KB	Output is correct
16	Correct	399 ms	61100 KB	Output is correct
17	Correct	453 ms	53800 KB	Output is correct
18	Correct	520 ms	52160 KB	Output is correct
19	Correct	512 ms	53012 KB	Output is correct
20	Correct	479 ms	51032 KB	Output is correct
21	Correct	537 ms	57600 KB	Output is correct
22	Correct	610 ms	59396 KB	Output is correct
23	Correct	561 ms	62216 KB	Output is correct
24	Correct	523 ms	59188 KB	Output is correct
25	Correct	507 ms	58476 KB	Output is correct