oj.uz

Submission #136262

# Submission time Handle Problem Language Result Execution time Memory
136262 2019-07-25T05:11:29 Z 김세빈(#3258) Link (CEOI06_link) C++14
16 / 100
 522 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] = 0;
			}
			
			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] = 1;
			}
			
			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] = 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 12 ms 12152 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 14 ms 12280 KB Output is correct
5 Incorrect 15 ms 12408 KB Output isn't correct
6 Incorrect 27 ms 13432 KB Output isn't correct
7 Incorrect 38 ms 14584 KB Output isn't correct
8 Incorrect 50 ms 15480 KB Output isn't correct
9 Incorrect 75 ms 17656 KB Output isn't correct
10 Incorrect 71 ms 16996 KB Output isn't correct
11 Correct 92 ms 16760 KB Output is correct
12 Incorrect 169 ms 21240 KB Output isn't correct
13 Correct 200 ms 24944 KB Output is correct
14 Incorrect 268 ms 26844 KB Output isn't correct
15 Incorrect 283 ms 26332 KB Output isn't correct
16 Incorrect 368 ms 31020 KB Output isn't correct
17 Incorrect 374 ms 29816 KB Output isn't correct
18 Incorrect 455 ms 35344 KB Output isn't correct
19 Incorrect 522 ms 34104 KB Output isn't correct
20 Incorrect 428 ms 32888 KB Output isn't correct
21 Incorrect 485 ms 34448 KB Output isn't correct
22 Incorrect 484 ms 34424 KB Output isn't correct
23 Incorrect 482 ms 37112 KB Output isn't correct
24 Incorrect 444 ms 33332 KB Output isn't correct
25 Incorrect 424 ms 32580 KB Output isn't correct