Submission #136485

#	Time	Username	Problem	Language	Result	Execution time	Memory
136485		imyujin	Link (CEOI06_link)	C++14	76 / 100	445 ms	37876 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[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;
	if(cyc.size() <= K) {
		ans++;
		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 (stderr)

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:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cyc.size() <= K) {
     ~~~~~~~~~~~^~~~
link.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < cyc.size() * 2; i++) {
                 ~~^~~~~~~~~~~~~~~~
link.cpp:59: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:62: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: 76 / 100