Submission #136441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136441	2019-07-25T10:10:14 Z	onjo0127	Link (CEOI06_link)	C++11	100 / 100	552 ms	51880 KB

link

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

const int _N = 500009, DBG = 0;
bool chk[_N];
int N, K, A[_N], vs[_N], dep[_N], rt[_N], rid[_N], ith[_N], p[_N], cs[_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[j] = j; cs[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[jt] = *st.begin();
					cs[jt] = *st.begin() - jt + M;
				}
				else {
					p[jt] = *kt;
					cs[jt] = *kt - jt;
				}
			}
			else {
				auto kt = st.lower_bound(jt + K - M);
				if(kt == st.end()) p[jt] = jt, cs[jt] = M;
				else p[jt] = *kt, cs[jt] = *kt - jt + M;
			}
			// printf("next[%d]: %d, cost: %d\n", jt, p[0][jt], cs[0][jt]);
		}

		st.insert(1e9);

		int mn = 1e9, stt = *st.begin();
		for(int j=stt-K; j<=stt; j++) {
			int jt = (j+M) % M;
			if(*st.lower_bound(jt) != jt) continue;
			int sum = 0, cnt = 0, now = jt;
			while(sum < M) {
				sum += cs[now];
				++cnt;
				now = p[now];
			}
			mn = min(mn, cnt);
		}
		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);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12152 KB	Output is correct
2	Correct	12 ms	12152 KB	Output is correct
3	Correct	13 ms	12152 KB	Output is correct
4	Correct	13 ms	12280 KB	Output is correct
5	Correct	15 ms	12456 KB	Output is correct
6	Correct	30 ms	14328 KB	Output is correct
7	Correct	42 ms	15348 KB	Output is correct
8	Correct	56 ms	17140 KB	Output is correct
9	Correct	103 ms	21428 KB	Output is correct
10	Correct	84 ms	20928 KB	Output is correct
11	Correct	148 ms	36968 KB	Output is correct
12	Correct	164 ms	23404 KB	Output is correct
13	Correct	223 ms	31752 KB	Output is correct
14	Correct	276 ms	36136 KB	Output is correct
15	Correct	341 ms	38960 KB	Output is correct
16	Correct	404 ms	48500 KB	Output is correct
17	Correct	454 ms	43592 KB	Output is correct
18	Correct	532 ms	46152 KB	Output is correct
19	Correct	526 ms	45860 KB	Output is correct
20	Correct	461 ms	43712 KB	Output is correct
21	Correct	497 ms	47260 KB	Output is correct
22	Correct	524 ms	49172 KB	Output is correct
23	Correct	552 ms	51880 KB	Output is correct
24	Correct	477 ms	49092 KB	Output is correct
25	Correct	468 ms	48364 KB	Output is correct