Submission #136296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136296	2019-07-25T05:56:00 Z	임유진(#3261)	Link (CEOI06_link)	C++14	40 / 100	775 ms	25972 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 ", 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 == K - 1 || !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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	12124 KB	Output is correct
2	Correct	13 ms	12152 KB	Output is correct
3	Incorrect	13 ms	12152 KB	Output isn't correct
4	Correct	13 ms	12152 KB	Output is correct
5	Incorrect	17 ms	12280 KB	Output isn't correct
6	Incorrect	25 ms	12920 KB	Output isn't correct
7	Correct	27 ms	13276 KB	Output is correct
8	Correct	34 ms	13896 KB	Output is correct
9	Correct	44 ms	15160 KB	Output is correct
10	Incorrect	45 ms	14996 KB	Output isn't correct
11	Correct	72 ms	19648 KB	Output is correct
12	Incorrect	88 ms	16412 KB	Output isn't correct
13	Correct	158 ms	18864 KB	Output is correct
14	Incorrect	115 ms	19704 KB	Output isn't correct
15	Correct	360 ms	22260 KB	Output is correct
16	Incorrect	151 ms	23288 KB	Output isn't correct
17	Incorrect	577 ms	24348 KB	Output isn't correct
18	Incorrect	182 ms	23668 KB	Output isn't correct
19	Incorrect	237 ms	24300 KB	Output isn't correct
20	Incorrect	769 ms	24480 KB	Output isn't correct
21	Incorrect	286 ms	25204 KB	Output isn't correct
22	Incorrect	359 ms	25300 KB	Output isn't correct
23	Incorrect	182 ms	24892 KB	Output isn't correct
24	Incorrect	373 ms	25972 KB	Output isn't correct
25	Correct	775 ms	25844 KB	Output is correct