Submission #136293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136293	2019-07-25T05:54:41 Z	임유진(#3261)	Link (CEOI06_link)	C++14	32 / 100	784 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-- >= 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 == 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

32.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Incorrect	13 ms	12152 KB	Output isn't correct
3	Incorrect	13 ms	12152 KB	Output isn't correct
4	Incorrect	13 ms	12152 KB	Output isn't correct
5	Incorrect	18 ms	12280 KB	Output isn't correct
6	Incorrect	22 ms	12920 KB	Output isn't correct
7	Correct	27 ms	13304 KB	Output is correct
8	Correct	34 ms	13948 KB	Output is correct
9	Correct	44 ms	15224 KB	Output is correct
10	Incorrect	46 ms	14968 KB	Output isn't correct
11	Correct	72 ms	19832 KB	Output is correct
12	Incorrect	84 ms	16348 KB	Output isn't correct
13	Correct	158 ms	18808 KB	Output is correct
14	Incorrect	117 ms	19708 KB	Output isn't correct
15	Correct	357 ms	22128 KB	Output is correct
16	Incorrect	171 ms	23544 KB	Output isn't correct
17	Incorrect	595 ms	24304 KB	Output isn't correct
18	Incorrect	188 ms	23692 KB	Output isn't correct
19	Incorrect	233 ms	24308 KB	Output isn't correct
20	Incorrect	784 ms	24524 KB	Output isn't correct
21	Incorrect	296 ms	25332 KB	Output isn't correct
22	Incorrect	372 ms	25332 KB	Output isn't correct
23	Incorrect	193 ms	24696 KB	Output isn't correct
24	Incorrect	376 ms	25968 KB	Output isn't correct
25	Correct	767 ms	25816 KB	Output is correct