Submission #136426

#	Time	Username	Problem	Language	Result	Execution time	Memory
136426		onjo0127	Link (CEOI06_link)	C++11	100 / 100	641 ms	61056 KiB

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 (stderr)

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 / 100