oj.uz

답안 #136498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136498 2019-07-25T11:27:24 Z imyujin Link (CEOI06_link) C++14
0 / 100
 383 ms 37620 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] = 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

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