oj.uz

Submission #136315

# Submission time Handle Problem Language Result Execution time Memory
136315 2019-07-25T06:42:54 Z 김세빈(#3258) Link (CEOI06_link) C++14
16 / 100
 475 ms 37368 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=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;
			}
			
			x = 0; y = 0;
			
			for(j=i; !chk1[j]; j=P[j]){
				if(!K[j]) x ++;
				else y ++;
				if(K[j] && !K[P[j]]) S[P[j]] = 1;
				chk1[j] = 1;
			}
			
			if(x == 0) continue;
			else if(y == 0){
				ans += (x - 1) / k + 1;
				continue;
			}
			
			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(S[j] && !K[P[j]]) S[P[j]] = S[j] + 1;
				chk1[j] = 1;
			}
			
			for(j=i; chk1[j]; j=P[j]){
				if(!K[j] && K[P[j]]) ans += (S[j] - 1) / k + 1;
				chk1[j] = 0;
			}
		}
	}
	
	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 13 ms 12280 KB Output is correct
2 Incorrect 13 ms 12280 KB Output isn't correct
3 Incorrect 13 ms 12280 KB Output isn't correct
4 Correct 13 ms 12280 KB Output is correct
5 Incorrect 14 ms 12408 KB Output isn't correct
6 Incorrect 26 ms 13432 KB Output isn't correct
7 Incorrect 36 ms 14584 KB Output isn't correct
8 Incorrect 56 ms 15608 KB Output isn't correct
9 Incorrect 65 ms 17528 KB Output isn't correct
10 Incorrect 65 ms 17016 KB Output isn't correct
11 Correct 86 ms 16740 KB Output is correct
12 Incorrect 166 ms 21240 KB Output isn't correct
13 Correct 189 ms 24956 KB Output is correct
14 Incorrect 247 ms 26776 KB Output isn't correct
15 Incorrect 287 ms 26360 KB Output isn't correct
16 Incorrect 352 ms 31104 KB Output isn't correct
17 Incorrect 370 ms 29816 KB Output isn't correct
18 Incorrect 453 ms 35320 KB Output isn't correct
19 Incorrect 450 ms 33912 KB Output isn't correct
20 Incorrect 432 ms 32892 KB Output isn't correct
21 Incorrect 429 ms 34552 KB Output isn't correct
22 Incorrect 450 ms 34424 KB Output isn't correct
23 Incorrect 475 ms 37368 KB Output isn't correct
24 Incorrect 473 ms 33400 KB Output isn't correct
25 Incorrect 439 ms 32508 KB Output isn't correct