oj.uz

답안 #136440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136440 2019-07-25T10:09:21 Z onjo0127 Link (CEOI06_link) C++11
92 / 100
 565 ms 51980 KB 
#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

# 결과 실행 시간 메모리 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