Submission #136291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136291	2019-07-25T05:53:13 Z	임유진(#3261)	Link (CEOI06_link)	C++14	16 / 100	776 ms	25908 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	1 ms	12152 KB	Output isn't correct
2	Incorrect	12 ms	12152 KB	Output isn't correct
3	Incorrect	12 ms	12152 KB	Output isn't correct
4	Incorrect	13 ms	12252 KB	Output isn't correct
5	Incorrect	13 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	33 ms	13900 KB	Output isn't correct
9	Correct	44 ms	15228 KB	Output is correct
10	Incorrect	45 ms	14968 KB	Output isn't correct
11	Correct	69 ms	19704 KB	Output is correct
12	Incorrect	96 ms	16332 KB	Output isn't correct
13	Correct	160 ms	18808 KB	Output is correct
14	Incorrect	119 ms	19704 KB	Output isn't correct
15	Correct	356 ms	22356 KB	Output is correct
16	Incorrect	154 ms	23416 KB	Output isn't correct
17	Incorrect	575 ms	24304 KB	Output isn't correct
18	Incorrect	188 ms	23724 KB	Output isn't correct
19	Incorrect	241 ms	24244 KB	Output isn't correct
20	Incorrect	772 ms	24564 KB	Output isn't correct
21	Incorrect	295 ms	25204 KB	Output isn't correct
22	Incorrect	364 ms	25372 KB	Output isn't correct
23	Incorrect	186 ms	24688 KB	Output isn't correct
24	Incorrect	406 ms	25844 KB	Output isn't correct
25	Incorrect	776 ms	25908 KB	Output isn't correct