Submission #136502

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136502	2019-07-25T11:37:14 Z	imyujin	Link (CEOI06_link)	C++14	100 / 100	394 ms	37664 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[2 * 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;
	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(cyc[i] == 1) go = K + 1;
		if(go-- > 0) col[i] = true;
		else col[i] = false;
	}
	for(int i = 0; i < go; i++) col[i] = true;
	bool done = true;
	for(int i = 0; i < cyc.size(); i++) done &= col[i];
	/*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;
	if(cyc.size() <= K) {
		ans++;
		return;
	}
	for(nex[0] = 0; col[nex[0] % cyc.size()]; nex[0]++);
	for(int i = 1; i < cyc.size(); i++) {
		nex[i] = nex[i - 1] - 1;
		if(nex[i] < 0) for(nex[i]++; col[(i + nex[i]) % cyc.size()]; nex[i]++);
	}
	//for(int i = 0; i < cyc.size(); i++) cout << nex[i] << " ";
	//cout << "\n";
	//cout << "ans = " << ans << "\n";
	int mn = cyc.size();
	for(int i = 0; i < K; i++) {
		int cnt = 0;
		for(int t = i + nex[i]; t < cyc.size() + i; t += K + nex[(t + K) % cyc.size()]) cnt++;
		//cout << cnt << " ";
		mn = min(mn, cnt);
	}
	//cout << "\n";
	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:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) done &= col[i];
                 ~~^~~~~~~~~~~~
link.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cyc.size() <= K) {
     ~~~~~~~~~~~^~~~
link.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:64:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int t = i + nex[i]; t < cyc.size() + i; t += K + nex[(t + K) % cyc.size()]) cnt++;
                           ~~^~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Correct	13 ms	12024 KB	Output is correct
3	Correct	13 ms	12152 KB	Output is correct
4	Correct	14 ms	12280 KB	Output is correct
5	Correct	14 ms	12280 KB	Output is correct
6	Correct	25 ms	13560 KB	Output is correct
7	Correct	34 ms	14456 KB	Output is correct
8	Correct	43 ms	15608 KB	Output is correct
9	Correct	62 ms	18420 KB	Output is correct
10	Correct	60 ms	17012 KB	Output is correct
11	Correct	93 ms	20976 KB	Output is correct
12	Correct	200 ms	21188 KB	Output is correct
13	Correct	189 ms	25980 KB	Output is correct
14	Correct	194 ms	25848 KB	Output is correct
15	Correct	255 ms	29428 KB	Output is correct
16	Correct	304 ms	30752 KB	Output is correct
17	Correct	338 ms	33700 KB	Output is correct
18	Correct	388 ms	34808 KB	Output is correct
19	Correct	385 ms	35188 KB	Output is correct
20	Correct	376 ms	36164 KB	Output is correct
21	Correct	388 ms	37664 KB	Output is correct
22	Correct	383 ms	36492 KB	Output is correct
23	Correct	386 ms	36208 KB	Output is correct
24	Correct	394 ms	36388 KB	Output is correct
25	Correct	387 ms	35916 KB	Output is correct