Submission #136498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136498	2019-07-25T11:27:24 Z	imyujin	Link (CEOI06_link)	C++14	0 / 100	383 ms	37620 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(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";
	int mn = 0;
	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:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cyc.size(); i++) done &= col[i];
                 ~~^~~~~~~~~~~~
link.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cyc.size() <= K) {
     ~~~~~~~~~~~^~~~
link.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < cyc.size(); i++) {
                 ~~^~~~~~~~~~~~
link.cpp:62: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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	12152 KB	Output isn't correct
2	Incorrect	12 ms	12152 KB	Output isn't correct
3	Incorrect	13 ms	12152 KB	Output isn't correct
4	Incorrect	14 ms	12280 KB	Output isn't correct
5	Incorrect	14 ms	12280 KB	Output isn't correct
6	Incorrect	25 ms	13560 KB	Output isn't correct
7	Incorrect	33 ms	14456 KB	Output isn't correct
8	Incorrect	41 ms	15480 KB	Output isn't correct
9	Incorrect	61 ms	18468 KB	Output isn't correct
10	Incorrect	59 ms	17036 KB	Output isn't correct
11	Incorrect	88 ms	20976 KB	Output isn't correct
12	Incorrect	140 ms	20984 KB	Output isn't correct
13	Incorrect	173 ms	25848 KB	Output isn't correct
14	Incorrect	227 ms	25968 KB	Output isn't correct
15	Incorrect	261 ms	29432 KB	Output isn't correct
16	Incorrect	380 ms	30828 KB	Output isn't correct
17	Incorrect	348 ms	33780 KB	Output isn't correct
18	Incorrect	383 ms	34756 KB	Output isn't correct
19	Incorrect	381 ms	35060 KB	Output isn't correct
20	Incorrect	363 ms	36084 KB	Output isn't correct
21	Incorrect	383 ms	37620 KB	Output isn't correct
22	Incorrect	382 ms	36596 KB	Output isn't correct
23	Incorrect	381 ms	36332 KB	Output isn't correct
24	Incorrect	373 ms	36280 KB	Output isn't correct
25	Incorrect	381 ms	36208 KB	Output isn't correct