Submission #136426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136426	2019-07-25T09:46:04 Z	onjo0127	Link (CEOI06_link)	C++11	100 / 100	641 ms	61056 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[15][_N], cs[15][_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();

	set<int> st;
	for(auto& it: R) {
		st.clear();
		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:122: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	13 ms	12152 KB	Output is correct
2	Correct	13 ms	12280 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	14968 KB	Output is correct
7	Correct	44 ms	15984 KB	Output is correct
8	Correct	72 ms	18264 KB	Output is correct
9	Correct	100 ms	24980 KB	Output is correct
10	Correct	90 ms	23696 KB	Output is correct
11	Correct	168 ms	51424 KB	Output is correct
12	Correct	175 ms	24080 KB	Output is correct
13	Correct	237 ms	37328 KB	Output is correct
14	Correct	365 ms	41852 KB	Output is correct
15	Correct	357 ms	47888 KB	Output is correct
16	Correct	454 ms	59464 KB	Output is correct
17	Correct	448 ms	52592 KB	Output is correct
18	Correct	553 ms	51752 KB	Output is correct
19	Correct	520 ms	52380 KB	Output is correct
20	Correct	519 ms	50576 KB	Output is correct
21	Correct	517 ms	56280 KB	Output is correct
22	Correct	524 ms	58116 KB	Output is correct
23	Correct	633 ms	61056 KB	Output is correct
24	Correct	506 ms	58020 KB	Output is correct
25	Correct	641 ms	57364 KB	Output is correct