Submission #136322

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136322	2019-07-25T07:00:17 Z	김세빈(#3258)	Link (CEOI06_link)	C++14	60 / 100	484 ms	48628 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, s=0; i<m+m; i++){
		for(; j<m+m && s<=k; j++) s += V[j];
		X[0][i] = j; s -= V[i];
	}
	
	X[0][m + m] = m + m;
	
	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:67: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:70: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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	12408 KB	Output isn't correct
2	Incorrect	13 ms	12408 KB	Output isn't correct
3	Correct	13 ms	12408 KB	Output is correct
4	Incorrect	14 ms	12536 KB	Output isn't correct
5	Incorrect	15 ms	12636 KB	Output isn't correct
6	Correct	28 ms	14456 KB	Output is correct
7	Correct	40 ms	15224 KB	Output is correct
8	Correct	51 ms	17020 KB	Output is correct
9	Correct	80 ms	22748 KB	Output is correct
10	Correct	84 ms	20724 KB	Output is correct
11	Correct	120 ms	38360 KB	Output is correct
12	Incorrect	165 ms	21476 KB	Output isn't correct
13	Correct	201 ms	32496 KB	Output is correct
14	Incorrect	282 ms	34060 KB	Output isn't correct
15	Correct	293 ms	38292 KB	Output is correct
16	Incorrect	368 ms	46192 KB	Output isn't correct
17	Correct	399 ms	41452 KB	Output is correct
18	Incorrect	478 ms	41768 KB	Output isn't correct
19	Incorrect	477 ms	41904 KB	Output isn't correct
20	Correct	484 ms	41112 KB	Output is correct
21	Correct	480 ms	46108 KB	Output is correct
22	Correct	447 ms	45804 KB	Output is correct
23	Correct	470 ms	48628 KB	Output is correct
24	Correct	448 ms	44804 KB	Output is correct
25	Incorrect	461 ms	43880 KB	Output isn't correct