Submission #136440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136440	2019-07-25T10:09:21 Z	onjo0127	Link (CEOI06_link)	C++11	92 / 100	565 ms	51980 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; j<stt+K+2; 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	16 ms	12152 KB	Output is correct
2	Incorrect	13 ms	12152 KB	Output isn't correct
3	Correct	16 ms	12156 KB	Output is correct
4	Correct	14 ms	12280 KB	Output is correct
5	Incorrect	15 ms	12408 KB	Output isn't correct
6	Correct	30 ms	14332 KB	Output is correct
7	Correct	43 ms	15348 KB	Output is correct
8	Correct	59 ms	17268 KB	Output is correct
9	Correct	93 ms	21488 KB	Output is correct
10	Correct	83 ms	21012 KB	Output is correct
11	Correct	149 ms	36924 KB	Output is correct
12	Correct	163 ms	23432 KB	Output is correct
13	Correct	229 ms	31656 KB	Output is correct
14	Correct	299 ms	36364 KB	Output is correct
15	Correct	327 ms	38832 KB	Output is correct
16	Correct	402 ms	48348 KB	Output is correct
17	Correct	446 ms	43584 KB	Output is correct
18	Correct	565 ms	46148 KB	Output is correct
19	Correct	516 ms	45744 KB	Output is correct
20	Correct	513 ms	43740 KB	Output is correct
21	Correct	522 ms	47236 KB	Output is correct
22	Correct	509 ms	49048 KB	Output is correct
23	Correct	557 ms	51980 KB	Output is correct
24	Correct	481 ms	49164 KB	Output is correct
25	Correct	490 ms	48364 KB	Output is correct