Submission #136502

#	Time	Username	Problem	Language	Result	Execution time	Memory
136502		imyujin	Link (CEOI06_link)	C++14	100 / 100	394 ms	37664 KiB

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 (stderr)

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 / 100