Submission #136332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136332	2019-07-25T07:07:25 Z	김세빈(#3258)	Link (CEOI06_link)	C++14	100 / 100	541 ms	48620 KB

link

#include <bits/stdc++.h>

using namespace std;

vector <int> V[505050];
int D[505050], P[505050];
int K[505050];
int X[20][505050];
int chk1[505050], chk2[505050];
int n, k, ans;

void dfs(int p, int v)
{
	for(int &t: V[p]){
		dfs(t, 0);
		K[p] = max(K[p], K[t] - 1);
	}
	
	if(!v && !K[p]){
		ans ++; K[p] = k;
	}
}

int calc(vector <int> &V)
{
	int m, i, j, t, s, ret;
	
	ret = 1e9;
	
	m = V.size();
	for(i=0; i<m; i++){
		V.push_back(V[i]);
	}
	
	for(i=0, j=0; i<=m+m; i++){
		for(; j<m+m && (j - i < k || !V[j]); j++);
		X[0][i] = j;
	}
	
	for(i=1; i<=19; i++){
		for(j=0; j<=m+m; j++){
			X[i][j] = X[i - 1][X[i - 1][j]];
		}
	}
	
	for(i=0; i<m; i++){
		s = 1; t = i;
		for(j=19; j>=0; j--){
			if(X[j][t] < m + i){
				t = X[j][t];
				s += 1 << j;
			}
		}
		ret = min(ret, s);
	}
	
	return ret;
}

int main()
{
	vector <int> T;
	int i, j, x, y;
	
	scanf("%d%d", &n, &k);
	
	for(i=1; i<=n; i++){
		scanf("%d%d", &x, &y);
		P[x] = y; D[y] ++;
	}
	
	K[1] = k + 1;
	
	for(i=1; i<=n; i++){
		for(j=i; !chk1[j]; j=P[j]) chk1[j] = i;
		if(chk1[j] != i) continue;
		for(; !chk2[j]; j=P[j]) chk2[j] = 1;
	}
	
	for(i=1; i<=n; i++){
		if(!chk2[i]){
			V[P[i]].push_back(i);
		}
	}
	
	for(i=1; i<=n; i++){
		if(chk2[i]) dfs(i, 1);
	}
	
	for(i=1; i<=n; i++){
		if(chk2[i]){
			for(j=i; chk2[j]; j=P[j]){
				K[P[j]] = max(K[P[j]], K[j] - 1);
				chk2[j] = 0;
			}
			
			for(j=i; chk1[j]; j=P[j]){
				K[P[j]] = max(K[P[j]], K[j] - 1);
				chk1[j] = 0;
			}
			
			T.clear();
			
			x = 0;
			
			for(j=i; !chk1[j]; j=P[j]){
				T.push_back(K[j]? 0 : 1);
				if(!K[j]) x ++;
				chk1[j] = 1;
			}
			
			if(x) ans += calc(T);
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:65: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:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12408 KB	Output is correct
2	Correct	13 ms	12408 KB	Output is correct
3	Correct	13 ms	12408 KB	Output is correct
4	Correct	14 ms	12536 KB	Output is correct
5	Correct	15 ms	12664 KB	Output is correct
6	Correct	28 ms	14328 KB	Output is correct
7	Correct	39 ms	15224 KB	Output is correct
8	Correct	51 ms	17016 KB	Output is correct
9	Correct	76 ms	22776 KB	Output is correct
10	Correct	74 ms	20720 KB	Output is correct
11	Correct	113 ms	38384 KB	Output is correct
12	Correct	145 ms	21384 KB	Output is correct
13	Correct	196 ms	32440 KB	Output is correct
14	Correct	268 ms	34068 KB	Output is correct
15	Correct	288 ms	38256 KB	Output is correct
16	Correct	382 ms	46060 KB	Output is correct
17	Correct	401 ms	41448 KB	Output is correct
18	Correct	479 ms	41840 KB	Output is correct
19	Correct	452 ms	41904 KB	Output is correct
20	Correct	433 ms	41200 KB	Output is correct
21	Correct	445 ms	45996 KB	Output is correct
22	Correct	452 ms	45740 KB	Output is correct
23	Correct	541 ms	48620 KB	Output is correct
24	Correct	463 ms	44880 KB	Output is correct
25	Correct	433 ms	43880 KB	Output is correct