oj.uz

답안 #136494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136494 2019-07-25T11:16:48 Z imyujin Link (CEOI06_link) C++14
76 / 100
 413 ms 37788 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) {
	//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] = 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

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() * 2; i++) {
                 ~~^~~~~~~~~~~~~~~~
link.cpp:60: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:63: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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Incorrect 13 ms 12152 KB Output isn't correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 14 ms 12280 KB Output is correct
5 Incorrect 14 ms 12408 KB Output isn't correct
6 Correct 26 ms 13568 KB Output is correct
7 Correct 33 ms 14456 KB Output is correct
8 Incorrect 43 ms 15608 KB Output isn't correct
9 Correct 66 ms 18552 KB Output is correct
10 Correct 68 ms 17140 KB Output is correct
11 Correct 101 ms 21380 KB Output is correct
12 Correct 137 ms 21048 KB Output is correct
13 Incorrect 201 ms 26100 KB Output isn't correct
14 Correct 232 ms 26144 KB Output is correct
15 Correct 272 ms 29932 KB Output is correct
16 Correct 347 ms 31244 KB Output is correct
17 Correct 366 ms 33992 KB Output is correct
18 Incorrect 410 ms 34996 KB Output isn't correct
19 Correct 406 ms 35416 KB Output is correct
20 Correct 393 ms 36396 KB Output is correct
21 Incorrect 401 ms 37788 KB Output isn't correct
22 Correct 399 ms 36848 KB Output is correct
23 Correct 413 ms 36456 KB Output is correct
24 Correct 409 ms 36580 KB Output is correct
25 Correct 403 ms 36212 KB Output is correct