Submission #136437

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136437	2019-07-25T10:07:27 Z	onjo0127	Link (CEOI06_link)	C++11	92 / 100	577 ms	51872 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[_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();

	set<int> st;
	for(auto& it: R) {
		st.clear();
		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; j<stt+K; j++) {
			int jt = j % 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

92.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Incorrect	12 ms	12152 KB	Output isn't correct
3	Correct	13 ms	12152 KB	Output is correct
4	Correct	14 ms	12280 KB	Output is correct
5	Incorrect	14 ms	12408 KB	Output isn't correct
6	Correct	30 ms	14456 KB	Output is correct
7	Correct	43 ms	15348 KB	Output is correct
8	Correct	58 ms	17140 KB	Output is correct
9	Correct	89 ms	21476 KB	Output is correct
10	Correct	83 ms	20888 KB	Output is correct
11	Correct	154 ms	36976 KB	Output is correct
12	Correct	218 ms	23400 KB	Output is correct
13	Correct	234 ms	31828 KB	Output is correct
14	Correct	291 ms	36264 KB	Output is correct
15	Correct	325 ms	38828 KB	Output is correct
16	Correct	384 ms	48344 KB	Output is correct
17	Correct	432 ms	43588 KB	Output is correct
18	Correct	514 ms	46012 KB	Output is correct
19	Correct	490 ms	45744 KB	Output is correct
20	Correct	474 ms	43736 KB	Output is correct
21	Correct	566 ms	47212 KB	Output is correct
22	Correct	513 ms	49104 KB	Output is correct
23	Correct	555 ms	51872 KB	Output is correct
24	Correct	505 ms	49076 KB	Output is correct
25	Correct	577 ms	48228 KB	Output is correct