Submission #136389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136389	2019-07-25T08:16:57 Z	송준혁(#3262)	Link (CEOI06_link)	C++14	16 / 100	1500 ms	6648 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[j]]) 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

16.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1560 ms	376 KB	Time limit exceeded
2	Execution timed out	1543 ms	376 KB	Time limit exceeded
3	Execution timed out	1555 ms	376 KB	Time limit exceeded
4	Correct	3 ms	376 KB	Output is correct
5	Execution timed out	1570 ms	376 KB	Time limit exceeded
6	Execution timed out	1552 ms	760 KB	Time limit exceeded
7	Execution timed out	1580 ms	888 KB	Time limit exceeded
8	Execution timed out	1559 ms	1272 KB	Time limit exceeded
9	Correct	36 ms	1656 KB	Output is correct
10	Execution timed out	1556 ms	1656 KB	Time limit exceeded
11	Correct	54 ms	2556 KB	Output is correct
12	Execution timed out	1570 ms	2680 KB	Time limit exceeded
13	Correct	100 ms	3448 KB	Output is correct
14	Execution timed out	1569 ms	3916 KB	Time limit exceeded
15	Execution timed out	1571 ms	4784 KB	Time limit exceeded
16	Incorrect	160 ms	5752 KB	Output isn't correct
17	Execution timed out	1559 ms	5880 KB	Time limit exceeded
18	Execution timed out	1572 ms	6648 KB	Time limit exceeded
19	Execution timed out	1572 ms	6500 KB	Time limit exceeded
20	Execution timed out	1560 ms	6392 KB	Time limit exceeded
21	Execution timed out	1577 ms	6520 KB	Time limit exceeded
22	Execution timed out	1568 ms	6392 KB	Time limit exceeded
23	Execution timed out	1561 ms	6520 KB	Time limit exceeded
24	Execution timed out	1582 ms	6392 KB	Time limit exceeded
25	Execution timed out	1566 ms	6392 KB	Time limit exceeded