Submission #136438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136438	2019-07-25T10:07:33 Z	imyujin	Link (CEOI06_link)	C++14	72 / 100	1500 ms	25820 KB

link

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int MAXK = 20005;

int A[MAXN], B[MAXN];
int ed[MAXN], ind[MAXN];
bool chk[MAXN], on[MAXN], cyc[MAXN];
vector<int> cnod[MAXN];
int cn;
queue<int> indz;

void searchgraph(int x) {
	//printf("searchgraph(%d)\n", x);
	chk[x] = on[x] = true;
	if(on[ed[x]]) {
		for(int t = x; !cyc[t]; t = ed[t]) {
			cyc[t] = true;
			cnod[cn].push_back(t);
		}
		cn++;
	}
	else if(!chk[ed[x]]) searchgraph(ed[x]);
	on[x] = false;
}

void movek(int x, int k) {
	for(; k-- >= 0; x = ed[x]) chk[x] = true;
	if(--ind[x] == 0) indz.push(x);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, K;
	int ans = 0;

	cin >> N >> K;
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

	for(int i = 0; i < N; i++) {
		ed[A[i]] = B[i];
		ind[B[i]]++;
	}

	for(int i = 1; i <= N; i++) if(!chk[i]) searchgraph(i);
	//printf("cn = %d\n", cn);
	//for(auto a : cnod[0]) printf("%d ", a);
	//printf("\n");
	for(int i = 1; i <= N; i++) chk[i] = false;
	movek(1, K);
	for(int i = 1; i <= N; i++) if(ind[i] == 0) indz.push(i);
	while(!indz.empty()) {
		if(!chk[indz.front()] && !cyc[indz.front()]) {
			//printf("indz = %d\n", indz.front());
			movek(indz.front(), K - 1);
			ans++;
		}
		indz.pop();
	}
	//for(int i = 1; i <= N; i++) printf("%d ", int(chk[i]));
	//printf("\nans = %d\n", ans);

	for(int i = 0; i < cn; i++) {
		//for(auto a : cnod[i]) printf("%d ", a);
		//printf("\n");
		bool done = true;
		for(auto a : cnod[i]) done &= chk[a];
		if(done) continue;
		if(cnod[i].size() <= K) {
			ans++;
			continue;
		}
		int mn = cnod[i].size();
		for(int j = 0; j < cnod[i].size(); j++) {
			int cnt = 0, t = j;
			while(t < cnod[i].size() + j) {
				while(t < cnod[i].size() + j && chk[cnod[i][t % cnod[i].size()]]) t++;
				if(t == cnod[i].size() + j) break;
				cnt++;
				t += K;
			}
			mn = min(mn, cnt);
		}
		ans += mn;
	}

	cout << ans;
	return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnod[i].size() <= K) {
      ~~~~~~~~~~~~~~~^~~~
link.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cnod[i].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~
link.cpp:77:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(t < cnod[i].size() + j) {
          ~~^~~~~~~~~~~~~~~~~~~~
link.cpp:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(t < cnod[i].size() + j && chk[cnod[i][t % cnod[i].size()]]) t++;
           ~~^~~~~~~~~~~~~~~~~~~~
link.cpp:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(t == cnod[i].size() + j) break;
        ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1

72.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Correct	12 ms	12152 KB	Output is correct
3	Correct	12 ms	12156 KB	Output is correct
4	Correct	17 ms	12136 KB	Output is correct
5	Incorrect	15 ms	12280 KB	Output isn't correct
6	Correct	28 ms	12948 KB	Output is correct
7	Correct	27 ms	13304 KB	Output is correct
8	Correct	35 ms	13816 KB	Output is correct
9	Correct	50 ms	15144 KB	Output is correct
10	Correct	63 ms	15000 KB	Output is correct
11	Correct	77 ms	19580 KB	Output is correct
12	Correct	111 ms	16400 KB	Output is correct
13	Correct	655 ms	18824 KB	Output is correct
14	Correct	699 ms	19644 KB	Output is correct
15	Execution timed out	1571 ms	22168 KB	Time limit exceeded
16	Execution timed out	1567 ms	23288 KB	Time limit exceeded
17	Correct	1296 ms	24304 KB	Output is correct
18	Correct	1362 ms	23724 KB	Output is correct
19	Execution timed out	1565 ms	24320 KB	Time limit exceeded
20	Execution timed out	1578 ms	24476 KB	Time limit exceeded
21	Incorrect	877 ms	25204 KB	Output isn't correct
22	Correct	970 ms	25340 KB	Output is correct
23	Correct	185 ms	24668 KB	Output is correct
24	Correct	985 ms	25820 KB	Output is correct
25	Execution timed out	1568 ms	25780 KB	Time limit exceeded