oj.uz

Submission #136255

# Submission time Handle Problem Language Result Execution time Memory
136255 2019-07-25T05:08:09 Z 김세빈(#3258) Link (CEOI06_link) C++14
0 / 100
 1500 ms 21112 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[505050];
int D[505050], P[505050];
int K[505050], S[505050];
bool 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[x] = 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] = 1;
		if(chk2[j]) continue;
		for(; !chk2[j]; j=P[j]) chk2[j] = 1;
		for(j=i; chk1[j]; j=P[j]) chk1[j] = 0;
	}
	
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 12280 KB Output isn't correct
2 Incorrect 12 ms 12252 KB Output isn't correct
3 Incorrect 13 ms 12280 KB Output isn't correct
4 Incorrect 15 ms 12280 KB Output isn't correct
5 Incorrect 18 ms 12408 KB Output isn't correct
6 Incorrect 45 ms 12784 KB Output isn't correct
7 Incorrect 59 ms 12924 KB Output isn't correct
8 Incorrect 208 ms 13436 KB Output isn't correct
9 Incorrect 145 ms 14072 KB Output isn't correct
10 Incorrect 280 ms 14020 KB Output isn't correct
11 Incorrect 115 ms 14840 KB Output isn't correct
12 Incorrect 585 ms 15864 KB Output isn't correct
13 Incorrect 672 ms 16632 KB Output isn't correct
14 Execution timed out 1571 ms 17528 KB Time limit exceeded
15 Incorrect 1093 ms 18440 KB Output isn't correct
16 Execution timed out 1573 ms 17784 KB Time limit exceeded
17 Incorrect 1260 ms 20184 KB Output isn't correct
18 Execution timed out 1575 ms 21112 KB Time limit exceeded
19 Execution timed out 1561 ms 21092 KB Time limit exceeded
20 Incorrect 1397 ms 21044 KB Output isn't correct
21 Execution timed out 1533 ms 21036 KB Time limit exceeded
22 Incorrect 1493 ms 21040 KB Output isn't correct
23 Execution timed out 1561 ms 21000 KB Time limit exceeded
24 Incorrect 1346 ms 21052 KB Output isn't correct
25 Incorrect 1433 ms 21040 KB Output isn't correct