oj.uz

Submission #170700

# Submission time Handle Problem Language Result Execution time Memory
170700 2019-12-26T06:02:33 Z youngyojun Split the Attractions (IOI19_split) C++17
18 / 100
 151 ms 18300 KB 
#include "split.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

const int MAXN = 100055;
const int MAXM = 200055;

vector<int> G[MAXN], T[MAXN];
vector<vector<int>> PathV;
int cnt[MAXN], col[MAXN], colcnt[MAXN];

int A[MAXM], B[MAXM];
bitset<MAXN> chk, colchk;

int ud[MAXN];
int Ans[MAXN];
int N, M, CA, CB, CC, CO[4], Rt, K;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

void normdfs(int i, int &c, int key) {
	if(!c) return;
	chk[i] = false; c--; Ans[i] = key;
	for(int v : G[i]) if(chk[v]) normdfs(v, c, key);
}
bool normAns() {
	for(int i = 0; i < N; i++) G[i].clear();
	for(int i = 0; i < M; i++) fg(G, A[i], B[i]);
	chk.reset();

	for(int i = 0; i < N; i++)
		if(Ans[i] < 1 || 2 < Ans[i]) Ans[i] = 3;

	int x = -1;
	for(int i = 0; i < N; i++) if(1 == Ans[i]) { x = i; chk[i] = true; }
	if(chk.count() < CA) return false;
	{ int c = CA; normdfs(x, c, -1); }
	for(int i = 0; i < N; i++) {
		if(1 == Ans[i]) Ans[i] = 3;
		else if(-1 == Ans[i]) Ans[i] = 1;
	}

	chk.reset();
	for(int i = 0; i < N; i++) if(2 == Ans[i]) { x = i; chk[i] = true; }
	if(chk.count() < CB) return false;
	{ int c = CB; normdfs(x, c, -2); }
	for(int i = 0; i < N; i++) {
		if(2 == Ans[i]) Ans[i] = 3;
		else if(-2 == Ans[i]) Ans[i] = 2;
	}

	return true;
}

void predfs(int i) {
	cnt[i] = 1;
	for(int v : G[i]) if(!cnt[v]) {
		predfs(v);
		cnt[i] += cnt[v];
	}
}
void cent(int &rt) {
	const int N = cnt[rt];
	for(int hi, hc;;) {
		hi = hc = -1;
		for(int v : G[rt]) if(cnt[v] < cnt[rt] && hc < cnt[v]) {
			hi = v; hc = cnt[v];
		}
		if(hc*2 <= N) break;
		cnt[rt] = N - hc;
		cnt[hi] = N;
		rt = hi;
	}
}

void treedfs(int i) {
	Ans[i] = 1;
	for(int v : G[i]) if(cnt[v] < cnt[i])
		treedfs(v);
}
bool solveTree() {
	for(int v : G[Rt]) if(CA <= cnt[v]) {
		fill(Ans, Ans+N, 2);
		treedfs(v);
		return true;
	}
	return false;
}

void precoldfs(int i) {
	colcnt[i] = 1;
	for(int v : G[i]) if(cnt[v] < cnt[i]) {
		col[v] = col[i];
		precoldfs(v);
		colcnt[i] += colcnt[v];
	}
}
void initNew() {
	for(int v : G[Rt]) {
		col[v] = K++;
		precoldfs(v);
	}
	for(int i = 0, a, b; i < M; i++) {
		a = col[A[i]];
		b = col[B[i]];
		if(a == b) continue;
		fg(T, a, b);
	}
}

void pathdfs(vector<int> &V, int i) {
	colchk[i] = true; V.eb(i);
	for(int v : T[i]) if(!colchk[v])
		pathdfs(V, v);
}
void getPath() {
	for(int i = 0; i < K; i++) if(!colchk[i]) {
		PathV.eb();
		pathdfs(PathV.back(), i);
	}
}

bool solve() {
	iota(CO, CO+4, 0);
	if(CA > CB) { swap(CA, CB); swap(CO[1], CO[2]); }
	if(CA > CC) { swap(CA, CC); swap(CO[1], CO[3]); }
	if(CB > CC) { swap(CB, CC); swap(CO[2], CO[3]); }

	iota(ud, ud+MAXN, 0);
	for(int i = 0, a, b; i < M; i++) {
		a = A[i]; b = B[i];
		if(uf(a) == uf(b)) continue;
		uf(a, b);
		fg(G, a, b);
	}
	predfs(0); cent(Rt);

	if(solveTree()) return true;

	initNew();
	getPath();

	for(; !PathV.empty();) {
		int sum = 0;
		for(int v : PathV.back()) sum += colcnt[v];
		if(sum < CA) PathV.pop_back();
		else break;
	}
	if(PathV.empty()) return false;

	vector<int> PV;
	{
		int sum = 0;
		for(int v : PathV.back()) {
			sum += colcnt[v];
			PV.eb(v);
			if(sum >= CA) break;
		}
	}

	fill(Ans, Ans+N, 2);
	colchk.reset();
	for(int v : PV) colchk[v] = true;
	for(int i = 0; i < N; i++) if(i != Rt && colchk[col[i]]) Ans[i] = 1;

	return true;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	::N = n; ::M = sz(p);
	::CA = a; ::CB = b; ::CC = c;
	for(int i = 0; i < ::M; i++) {
		::A[i] = p[i];
		::B[i] = q[i];
	}
	if(!solve() || !normAns()) return vector<int>(::N, 0);
	vector<int> res;
	for(int i = 0; i < ::N; i++) {
		if(1 == ::Ans[i]) res.eb(::CO[1]);
		else if(2 == ::Ans[i]) res.eb(::CO[2]);
		else res.eb(::CO[3]);
	}
	return res;
}

Compilation message

split.cpp: In function 'bool normAns()':
split.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(chk.count() < CA) return false;
     ~~~~~~~~~~~~^~~~
split.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(chk.count() < CB) return false;
     ~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5520 KB ok, correct split
2 Correct 6 ms 5368 KB ok, correct split
3 Correct 6 ms 5496 KB ok, correct split
4 Correct 6 ms 5492 KB ok, correct split
5 Correct 6 ms 5496 KB ok, correct split
6 Correct 6 ms 5496 KB ok, correct split
7 Correct 112 ms 16872 KB ok, correct split
8 Correct 100 ms 15480 KB ok, correct split
9 Correct 126 ms 15736 KB ok, correct split
10 Correct 110 ms 17272 KB ok, correct split
11 Correct 125 ms 16736 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB ok, correct split
2 Correct 6 ms 5368 KB ok, correct split
3 Correct 6 ms 5368 KB ok, correct split
4 Correct 126 ms 14832 KB ok, correct split
5 Correct 95 ms 12700 KB ok, correct split
6 Correct 109 ms 17656 KB ok, correct split
7 Correct 107 ms 15996 KB ok, correct split
8 Correct 151 ms 16244 KB ok, correct split
9 Correct 108 ms 13048 KB ok, correct split
10 Correct 98 ms 13428 KB ok, correct split
11 Correct 75 ms 13680 KB ok, correct split
12 Correct 79 ms 13552 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5368 KB ok, correct split
2 Correct 114 ms 12900 KB ok, correct split
3 Correct 39 ms 8440 KB ok, correct split
4 Correct 6 ms 5368 KB ok, correct split
5 Correct 111 ms 14584 KB ok, correct split
6 Correct 116 ms 14464 KB ok, correct split
7 Correct 109 ms 13664 KB ok, correct split
8 Correct 110 ms 15056 KB ok, correct split
9 Correct 104 ms 14204 KB ok, correct split
10 Correct 32 ms 8284 KB ok, no valid answer
11 Correct 45 ms 9080 KB ok, no valid answer
12 Correct 101 ms 16476 KB ok, no valid answer
13 Correct 107 ms 14164 KB ok, no valid answer
14 Incorrect 101 ms 18300 KB invalid split: #1=66666, #2=1, #3=33333

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5368 KB ok, correct split
2 Incorrect 6 ms 5496 KB invalid split: #1=1, #2=2, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5520 KB ok, correct split
2 Correct 6 ms 5368 KB ok, correct split
3 Correct 6 ms 5496 KB ok, correct split
4 Correct 6 ms 5492 KB ok, correct split
5 Correct 6 ms 5496 KB ok, correct split
6 Correct 6 ms 5496 KB ok, correct split
7 Correct 112 ms 16872 KB ok, correct split
8 Correct 100 ms 15480 KB ok, correct split
9 Correct 126 ms 15736 KB ok, correct split
10 Correct 110 ms 17272 KB ok, correct split
11 Correct 125 ms 16736 KB ok, correct split
12 Correct 6 ms 5496 KB ok, correct split
13 Correct 6 ms 5368 KB ok, correct split
14 Correct 6 ms 5368 KB ok, correct split
15 Correct 126 ms 14832 KB ok, correct split
16 Correct 95 ms 12700 KB ok, correct split
17 Correct 109 ms 17656 KB ok, correct split
18 Correct 107 ms 15996 KB ok, correct split
19 Correct 151 ms 16244 KB ok, correct split
20 Correct 108 ms 13048 KB ok, correct split
21 Correct 98 ms 13428 KB ok, correct split
22 Correct 75 ms 13680 KB ok, correct split
23 Correct 79 ms 13552 KB ok, correct split
24 Correct 6 ms 5368 KB ok, correct split
25 Correct 114 ms 12900 KB ok, correct split
26 Correct 39 ms 8440 KB ok, correct split
27 Correct 6 ms 5368 KB ok, correct split
28 Correct 111 ms 14584 KB ok, correct split
29 Correct 116 ms 14464 KB ok, correct split
30 Correct 109 ms 13664 KB ok, correct split
31 Correct 110 ms 15056 KB ok, correct split
32 Correct 104 ms 14204 KB ok, correct split
33 Correct 32 ms 8284 KB ok, no valid answer
34 Correct 45 ms 9080 KB ok, no valid answer
35 Correct 101 ms 16476 KB ok, no valid answer
36 Correct 107 ms 14164 KB ok, no valid answer
37 Incorrect 101 ms 18300 KB invalid split: #1=66666, #2=1, #3=33333