Submission #136418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136418	2019-07-25T09:26:13 Z	imyujin	Link (CEOI06_link)	C++14	88 / 100	1145 ms	25916 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 <= K; j++) if(j == K - 1 || !chk[cnod[i][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: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

88.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	12152 KB	Output is correct
4	Correct	13 ms	12152 KB	Output is correct
5	Incorrect	14 ms	12280 KB	Output isn't correct
6	Correct	22 ms	13048 KB	Output is correct
7	Correct	27 ms	13288 KB	Output is correct
8	Correct	33 ms	13944 KB	Output is correct
9	Correct	44 ms	15144 KB	Output is correct
10	Correct	43 ms	14968 KB	Output is correct
11	Correct	69 ms	19704 KB	Output is correct
12	Correct	85 ms	16376 KB	Output is correct
13	Correct	288 ms	18808 KB	Output is correct
14	Correct	119 ms	19684 KB	Output is correct
15	Correct	203 ms	22128 KB	Output is correct
16	Incorrect	160 ms	23388 KB	Output isn't correct
17	Correct	397 ms	24276 KB	Output is correct
18	Correct	216 ms	23684 KB	Output is correct
19	Correct	285 ms	24280 KB	Output is correct
20	Correct	422 ms	24436 KB	Output is correct
21	Incorrect	369 ms	25208 KB	Output isn't correct
22	Correct	575 ms	25428 KB	Output is correct
23	Correct	185 ms	24688 KB	Output is correct
24	Correct	233 ms	25892 KB	Output is correct
25	Correct	1145 ms	25916 KB	Output is correct