Submission #170702

#	Time	Username	Problem	Language	Result	Execution time	Memory
170702		youngyojun	Split the Attractions (IOI19_split)	C++17	40 / 100	171 ms	17924 KiB

split

#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++) if(A[i] != Rt && B[i] != Rt) {
		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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36