Submission #136325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136325	2019-07-25T07:02:26 Z	김세빈(#3258)	Link (CEOI06_link)	C++14	0 / 100	500 ms	48748 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; i<m+m; i++){
		for(; j<m+m && (j - i <= k || V[j]); j++);
		X[0][i] = j;
	}
	
	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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	12408 KB	Output isn't correct
2	Incorrect	14 ms	12408 KB	Output isn't correct
3	Incorrect	13 ms	12412 KB	Output isn't correct
4	Incorrect	17 ms	12536 KB	Output isn't correct
5	Incorrect	18 ms	12664 KB	Output isn't correct
6	Incorrect	28 ms	14328 KB	Output isn't correct
7	Incorrect	39 ms	15224 KB	Output isn't correct
8	Incorrect	50 ms	17116 KB	Output isn't correct
9	Incorrect	72 ms	22776 KB	Output isn't correct
10	Incorrect	73 ms	20712 KB	Output isn't correct
11	Incorrect	127 ms	38256 KB	Output isn't correct
12	Incorrect	164 ms	21368 KB	Output isn't correct
13	Incorrect	207 ms	32620 KB	Output isn't correct
14	Incorrect	273 ms	34036 KB	Output isn't correct
15	Incorrect	286 ms	38380 KB	Output isn't correct
16	Incorrect	374 ms	46320 KB	Output isn't correct
17	Incorrect	380 ms	41424 KB	Output isn't correct
18	Incorrect	462 ms	41672 KB	Output isn't correct
19	Incorrect	450 ms	41976 KB	Output isn't correct
20	Incorrect	439 ms	41072 KB	Output isn't correct
21	Incorrect	431 ms	46044 KB	Output isn't correct
22	Incorrect	428 ms	45804 KB	Output isn't correct
23	Incorrect	500 ms	48748 KB	Output isn't correct
24	Incorrect	450 ms	44904 KB	Output isn't correct
25	Incorrect	497 ms	43880 KB	Output isn't correct