oj.uz

답안 #136503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136503 2019-07-25T11:38:31 Z imyujin Link (CEOI06_link) C++14
100 / 100
 458 ms 37592 KB 
#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

# 결과 실행 시간 메모리 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