Submission #136392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136392	2019-07-25T08:25:59 Z	송준혁(#3262)	Link (CEOI06_link)	C++14	100 / 100	280 ms	6748 KB

link

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, K, ans;
int M[505050];
int nx[505050], deg[505050];
int C[505050], J[505050], P;
queue<int> Q;

void f(int u, int d){
	if (M[u] >= d) return;
	M[u] = d;
	f(nx[u], d-1);
}

int main(){
	scanf("%d %d", &N, &K);
	for (int i=1; i<=N; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		nx[u] = v, deg[v]++;
	}
	for (int i=1; i<=N; i++) if (deg[i] == 0) Q.push(i);
	f(1, K+1);
	while (!Q.empty()){
		int u = Q.front();
		deg[nx[u]]--;
		Q.pop();
		if (deg[nx[u]] == 0) Q.push(nx[u]);
		if (M[u]) continue;
		f(u, K);
		ans++;
	}
	for (int i=1; i<=N; i++){
		if (M[i]) continue;
		int u = i;
		P = 1, C[P] = u, u = nx[u];
		while (C[1] != u){
			P++;
			C[P] = u;
			u = nx[u];
		}
		if (P <= K) ans++;
		else{
			int Min = 1234567890, cnt;
			int p = P+1;
			for (int j = P; j>0; j--){
				if (M[C[j]]) J[j] = p;
				else p = j;
			}
			p = 1, cnt = 0;
			while (p <= P){
				if (M[C[p]]) p = J[p];
				else{
					cnt++;
					p = p+K;
				}
			}
			Min = min(Min, cnt);

			for (int j=1; j<K; j++){
				p = j+1, cnt = 1;
				while (p <= P-(K-j)){
					if (M[C[p]]) p = J[p];
					else{
						cnt++;
						p = p+K;
					}
				}
				Min = min(Min, cnt);
			}

			ans += Min;
		}
		for (int i=1; i<=P; i++) M[C[i]] = 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:19: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:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	11 ms	760 KB	Output is correct
7	Correct	17 ms	1016 KB	Output is correct
8	Correct	25 ms	1180 KB	Output is correct
9	Correct	35 ms	1656 KB	Output is correct
10	Correct	37 ms	1656 KB	Output is correct
11	Correct	55 ms	2680 KB	Output is correct
12	Correct	87 ms	2712 KB	Output is correct
13	Correct	107 ms	3492 KB	Output is correct
14	Correct	126 ms	4344 KB	Output is correct
15	Correct	156 ms	4856 KB	Output is correct
16	Correct	184 ms	5880 KB	Output is correct
17	Correct	207 ms	5948 KB	Output is correct
18	Correct	246 ms	6692 KB	Output is correct
19	Correct	252 ms	6556 KB	Output is correct
20	Correct	280 ms	6460 KB	Output is correct
21	Correct	235 ms	6624 KB	Output is correct
22	Correct	239 ms	6748 KB	Output is correct
23	Correct	225 ms	6520 KB	Output is correct
24	Correct	223 ms	6520 KB	Output is correct
25	Correct	243 ms	6596 KB	Output is correct