oj.uz

Submission #136260

# Submission time Handle Problem Language Result Execution time Memory
136260 2019-07-25T05:10:26 Z 김세빈(#3258) Link (CEOI06_link) C++14
16 / 100
 460 ms 37112 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[505050];
int D[505050], P[505050];
int K[505050], S[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 main()
{
	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=2; i<=n; i++){
		if(!D[i]) ans ++, K[i] = k;
	}
	
	for(i=1; i<=n; i++){
		for(j=i; !chk1[j] && !chk2[j]; j=P[j]) chk1[j] = i;
		if(chk1[j] != i || chk2[j]) 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] = 1;
			}
			
			x = 0; y = 0;
			
			for(j=i; chk1[j]; j=P[j]){
				if(!K[P[j]]) x ++;
				else y ++;
				if(K[j] && !K[P[j]]) S[P[j]] = 1;
				chk1[j] = 0;
			}
			
			if(x == 0) continue;
			else if(y == 0) ans += (x - 1) / k + 1;
			
			for(j=i; !chk1[j]; j=P[j]){
				if(S[j] && !K[P[j]]) S[P[j]] = S[j] + 1;
				chk1[j] = 1;
			}
			
			for(j=i; chk1[j]; j=P[j]){
				if(S[j] && !K[P[j]]) S[P[j]] = S[j] + 1;
				chk1[j] = 0;
			}
			
			for(j=i; !chk1[j]; j=P[j]){
				if(!K[j] && K[P[j]]) ans += (S[j] - 1) / k + 1;
				chk1[j] = 1;
			}
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:27: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:30: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
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12280 KB Output is correct
2 Incorrect 13 ms 12152 KB Output isn't correct
3 Incorrect 13 ms 12280 KB Output isn't correct
4 Correct 14 ms 12284 KB Output is correct
5 Incorrect 15 ms 12408 KB Output isn't correct
6 Incorrect 26 ms 13432 KB Output isn't correct
7 Incorrect 38 ms 14584 KB Output isn't correct
8 Incorrect 48 ms 15480 KB Output isn't correct
9 Incorrect 67 ms 17528 KB Output isn't correct
10 Incorrect 69 ms 17016 KB Output isn't correct
11 Correct 95 ms 16760 KB Output is correct
12 Incorrect 166 ms 21308 KB Output isn't correct
13 Correct 203 ms 24980 KB Output is correct
14 Incorrect 253 ms 26716 KB Output isn't correct
15 Incorrect 284 ms 26360 KB Output isn't correct
16 Incorrect 358 ms 31096 KB Output isn't correct
17 Incorrect 345 ms 29688 KB Output isn't correct
18 Incorrect 456 ms 35376 KB Output isn't correct
19 Incorrect 441 ms 34040 KB Output isn't correct
20 Incorrect 411 ms 32820 KB Output isn't correct
21 Incorrect 425 ms 34656 KB Output isn't correct
22 Incorrect 418 ms 34296 KB Output isn't correct
23 Incorrect 460 ms 37112 KB Output isn't correct
24 Incorrect 425 ms 33404 KB Output isn't correct
25 Incorrect 420 ms 32248 KB Output isn't correct