Submission #136289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136289	2019-07-25T05:52:11 Z	임유진(#3261)	Link (CEOI06_link)	C++14	16 / 100	852 ms	25968 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--; 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 ", int(chk[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 == 0 || chk[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

16.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	12152 KB	Output isn't correct
2	Incorrect	13 ms	12152 KB	Output isn't correct
3	Incorrect	13 ms	12280 KB	Output isn't correct
4	Incorrect	14 ms	12280 KB	Output isn't correct
5	Incorrect	14 ms	12280 KB	Output isn't correct
6	Incorrect	22 ms	12920 KB	Output isn't correct
7	Incorrect	27 ms	13304 KB	Output isn't correct
8	Incorrect	35 ms	13944 KB	Output isn't correct
9	Correct	44 ms	15100 KB	Output is correct
10	Incorrect	49 ms	14968 KB	Output isn't correct
11	Correct	74 ms	19704 KB	Output is correct
12	Incorrect	88 ms	16376 KB	Output isn't correct
13	Correct	229 ms	18908 KB	Output is correct
14	Incorrect	127 ms	19832 KB	Output isn't correct
15	Correct	329 ms	22348 KB	Output is correct
16	Incorrect	162 ms	23416 KB	Output isn't correct
17	Incorrect	504 ms	24304 KB	Output isn't correct
18	Incorrect	206 ms	23796 KB	Output isn't correct
19	Incorrect	273 ms	24268 KB	Output isn't correct
20	Incorrect	852 ms	24668 KB	Output isn't correct
21	Incorrect	322 ms	25368 KB	Output isn't correct
22	Incorrect	440 ms	25300 KB	Output isn't correct
23	Incorrect	210 ms	24660 KB	Output isn't correct
24	Incorrect	407 ms	25788 KB	Output isn't correct
25	Incorrect	826 ms	25968 KB	Output isn't correct