Submission #136503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136503	2019-07-25T11:38:31 Z	imyujin	Link (CEOI06_link)	C++14	100 / 100	458 ms	37592 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) {
	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) {
	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;
		else 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];
	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]++);
	}
	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++;
		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:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) done &= col[i];
                 ~~^~~~~~~~~~~~
link.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cyc.size() <= K) {
     ~~~~~~~~~~~^~~~
link.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:54: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	12156 KB	Output is correct
2	Correct	12 ms	12152 KB	Output is correct
3	Correct	12 ms	12152 KB	Output is correct
4	Correct	13 ms	12284 KB	Output is correct
5	Correct	14 ms	12280 KB	Output is correct
6	Correct	25 ms	13560 KB	Output is correct
7	Correct	32 ms	14460 KB	Output is correct
8	Correct	41 ms	15608 KB	Output is correct
9	Correct	66 ms	18428 KB	Output is correct
10	Correct	60 ms	17012 KB	Output is correct
11	Correct	98 ms	20888 KB	Output is correct
12	Correct	138 ms	21112 KB	Output is correct
13	Correct	177 ms	25976 KB	Output is correct
14	Correct	217 ms	25848 KB	Output is correct
15	Correct	254 ms	29432 KB	Output is correct
16	Correct	314 ms	30856 KB	Output is correct
17	Correct	458 ms	33736 KB	Output is correct
18	Correct	387 ms	34912 KB	Output is correct
19	Correct	371 ms	35156 KB	Output is correct
20	Correct	407 ms	36212 KB	Output is correct
21	Correct	387 ms	37592 KB	Output is correct
22	Correct	392 ms	36712 KB	Output is correct
23	Correct	389 ms	36208 KB	Output is correct
24	Correct	372 ms	36464 KB	Output is correct
25	Correct	379 ms	35956 KB	Output is correct