Submission #136428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136428	2019-07-25T09:47:02 Z	onjo0127	Link (CEOI06_link)	C++11	92 / 100	597 ms	58456 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[11][_N], cs[11][_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

92.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	16 ms	12408 KB	Output is correct
5	Correct	18 ms	12536 KB	Output is correct
6	Correct	34 ms	14840 KB	Output is correct
7	Correct	49 ms	15860 KB	Output is correct
8	Correct	67 ms	18104 KB	Output is correct
9	Correct	89 ms	23896 KB	Output is correct
10	Correct	86 ms	22900 KB	Output is correct
11	Incorrect	161 ms	47192 KB	Output isn't correct
12	Correct	173 ms	23860 KB	Output is correct
13	Correct	237 ms	35924 KB	Output is correct
14	Correct	286 ms	40236 KB	Output is correct
15	Correct	343 ms	45360 KB	Output is correct
16	Correct	408 ms	56244 KB	Output is correct
17	Correct	448 ms	50120 KB	Output is correct
18	Incorrect	530 ms	50108 KB	Output isn't correct
19	Correct	513 ms	50608 KB	Output is correct
20	Correct	478 ms	48464 KB	Output is correct
21	Correct	523 ms	53636 KB	Output is correct
22	Correct	533 ms	55576 KB	Output is correct
23	Correct	597 ms	58456 KB	Output is correct
24	Correct	558 ms	55740 KB	Output is correct
25	Correct	572 ms	54632 KB	Output is correct