Submission #136481

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136481	2019-07-25T11:06:25 Z	imyujin	Link (CEOI06_link)	C++14	52 / 100	1500 ms	37756 KB

link

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int N, K;
int A[MAXN], B[MAXN];
int ed[MAXN];
vector<int> chi[MAXN];
bool chk[MAXN], col[MAXN];
vector<int> cyc;
int nex[MAXN];
int ans;

int dfs(int x) {
	//cout << "dfs(" << x << ")\n";
	chk[x] = true;
	int go = 0;
	for(auto a : chi[x]) go = max(go, dfs(a));
	if(x == 1) go = K - 1;
	else if(go-- == 0) {
		ans++;
		go = K - 1;
	}
	return go;
}

void searchgraph(int x) {
	//cout << "searchgraph(" << x << ")\n";
	for(; !chk[x]; x = ed[x]) chk[x] = true;
	for(cyc.clear(); cyc.empty() || cyc[0] != x; x = ed[x]) cyc.push_back(x);
	int go = 0;
	bool done = true;
	for(int i = 0; i < cyc.size(); i++) {
		for(auto a : chi[cyc[i]]) if(a != cyc[(i + cyc.size() - 1) % cyc.size()]) go = max(go, dfs(a));
		//cout << "go = " << go << "\n";
		if(go-- > 0) col[i] = true;
		else done = col[i] = false;
	}
	for(int i = 0; i < go; i++) col[i] = true;
	/*for(int i = 0; i < cyc.size(); i++) cout << cyc[i] << " ";
	cout << "\n";
	for(int i = 0; i < cyc.size(); i++) cout << int(col[i]) << " ";
	cout << "\n";
	cout << int(done) << "\n";*/
	if(done) return;
	for(nex[0] = K; col[nex[0] % cyc.size()]; nex[0]++);
	for(int i = 1; i < cyc.size() * 2; i++) {
		nex[i] = nex[i - 1];
		if(nex[i] < i + K) for(nex[i]++; col[nex[i] % cyc.size()]; nex[i]++);
	}
	//for(int i = 0; i < cyc.size(); i++) cout << nex[i] << " ";
	//cout << "\n";
	int mn = 0;
	for(int t = nex[0]; t < cyc.size() + nex[0]; t = nex[t]) mn++;
	for(int i = 0; i < K; i++) {
		int cnt = 0;
		for(int t = i; t < cyc.size() + i; t = nex[t]) cnt++;
		mn = min(mn, cnt);
	}
	ans += mn;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(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];
		chi[B[i]].push_back(A[i]);
	}

	for(int i = 1; i <= N; i++) if(!chk[i]) searchgraph(i);
	cout << ans;
	return 0;
}

Compilation message

link.cpp: In function 'void searchgraph(int)':
link.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < cyc.size() * 2; i++) {
                 ~~^~~~~~~~~~~~~~~~
link.cpp:55:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t = nex[0]; t < cyc.size() + nex[0]; t = nex[t]) mn++;
                      ~~^~~~~~~~~~~~~~~~~~~~~
link.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int t = i; t < cyc.size() + i; t = nex[t]) cnt++;
                  ~~^~~~~~~~~~~~~~~~

Subtask #1

52.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12116 KB	Output is correct
2	Incorrect	12 ms	12152 KB	Output isn't correct
3	Correct	13 ms	12156 KB	Output is correct
4	Correct	13 ms	12152 KB	Output is correct
5	Incorrect	14 ms	12280 KB	Output isn't correct
6	Execution timed out	1560 ms	13436 KB	Time limit exceeded
7	Execution timed out	1559 ms	14328 KB	Time limit exceeded
8	Incorrect	41 ms	15608 KB	Output isn't correct
9	Execution timed out	1542 ms	18044 KB	Time limit exceeded
10	Correct	59 ms	17056 KB	Output is correct
11	Execution timed out	1556 ms	19704 KB	Time limit exceeded
12	Correct	128 ms	21032 KB	Output is correct
13	Incorrect	180 ms	26124 KB	Output isn't correct
14	Correct	228 ms	26080 KB	Output is correct
15	Correct	255 ms	29788 KB	Output is correct
16	Correct	304 ms	31152 KB	Output is correct
17	Correct	330 ms	33944 KB	Output is correct
18	Incorrect	392 ms	34896 KB	Output isn't correct
19	Execution timed out	1530 ms	34432 KB	Time limit exceeded
20	Correct	387 ms	36356 KB	Output is correct
21	Incorrect	399 ms	37756 KB	Output isn't correct
22	Correct	406 ms	36848 KB	Output is correct
23	Execution timed out	1539 ms	35052 KB	Time limit exceeded
24	Correct	402 ms	36620 KB	Output is correct
25	Correct	395 ms	36336 KB	Output is correct