Submission #143804

#	Time	Username	Problem	Language	Result	Execution time	Memory
143804		ainta	Split the Attractions (IOI19_split)	C++17	100 / 100	256 ms	40256 KiB

split

#include "split.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 201000

using namespace std;

vector<int>E[N_], T[N_], GP[N_], G[N_];
int n, AA, BB, CC, par[N_], vis[N_], C[N_], Where[N_], chk[N_];
void DFS1(int a) {
	vis[a] = 1;
	C[a] = 1;
	for (auto &x : E[a]) {
		if (vis[x]) continue;
		par[x] = a;
		T[a].push_back(x);
		T[x].push_back(a);
		DFS1(x);
		C[a] += C[x];
	}
}


int M1=1, M2=2, M3=3;

vector<int>TP;
void DFS2(int a, int pp) {
	TP.push_back(a);
	for (auto &x : T[a]) {
		if (x == pp)continue;
		DFS2(x, a);
	}
}

void DFS3(int a, int pp, int ppp) {
	GP[ppp].push_back(a);
	Where[a] = ppp;
	C[a] = 1;
	for (auto &x : T[a]) {
		if (x != pp) {
			DFS3(x, a, ppp);
			C[a] += C[x];
		}
	}
}

int val[N_], szlim;

void DFS4(int a){
	vis[a] = 1;
	if (szlim) {
		TP.push_back(a);
		szlim--;
	}
	for (auto &x : E[a]) {
		if (val[x] && !vis[x])DFS4(x);
	}
}

vector<int>Conn(vector<int> A, int num) {
	int i;
	for (i = 1; i <= n; i++)val[i] = 0, vis[i] = 0;
	for (auto &x : A)val[x] = 1;
	TP.clear();
	szlim = num;
	DFS4(A[0]);
	return TP;
}

vector<int> Remaining(vector<int> A) {
	int i;
	for (i = 1; i <= n; i++)vis[i] = 0;
	for (auto &x : A)vis[x] = 1;
	vector<int>res;
	for (i = 1; i <= n; i++)if (!vis[i])res.push_back(i);
	return res;
}

vector<int>MakeAns(vector<int>A, vector<int>B) {
	if (A.size() > B.size()) {
		swap(A, B);
	}
	A = Conn(A, AA);
	B = Conn(B, BB);
	vector<int>res(n);
	for (int i = 0; i < n; i++)res[i] = M3;
	for (auto &x : A)res[x-1] = M1;
	for (auto &x : B)res[x-1] = M2;
	return res;
}

int sum;
void Go(int a) {
	vis[a] = 1;
	TP.push_back(a);
	sum += C[a];
	if (sum >= AA)return;
	for (auto &x : G[a]) {
		if (!vis[x]) {
			Go(x);
			if (sum >= AA)return;
		}
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	if (a > b)swap(a, b),swap(M1,M2);
	if (a > c)swap(a, c),swap(M1,M3);
	if (b > c)swap(b, c),swap(M2,M3);
	AA = a, BB = b, CC = c;
	int i;
	for (i = 0; i < p.size(); i++) {
		E[p[i]+1].push_back(q[i]+1);
		E[q[i]+1].push_back(p[i]+1);
	}
	DFS1(1);

	for (i = 1; i <= n; i++) {
		if ((C[i] >= AA && n - C[i] >= BB)|| (C[i] >= BB && n - C[i] >= AA)) {
			TP.clear();
			DFS2(i, par[i]);
			vector<int>TP2 = Remaining(TP);
			return MakeAns(TP, TP2);
		}
	}

	int Mn = 1e9, mid = -1;
	for (i = 1; i <= n; i++) {
		if (Mn > C[i] && C[i] * 2 > n)Mn = C[i], mid = i;
	}
	for (auto &x : T[mid]) {
		chk[x] = 1;
		DFS3(x, mid, x);
	}

	for (i = 1; i <= n; i++) {
		for (auto &x : E[i]) {
			if (i == mid || x == mid)continue;
			if (Where[i] != Where[x]) {
				G[Where[i]].push_back(Where[x]);
			}
		}
	}

	for (i = 1; i <= n; i++)vis[i] = 0;
	for (auto &t : T[mid]) {
		sum = 0;
		TP.clear();
		Go(T[mid][0]);
		if (sum >= AA) {

			vector<int>TT;
			for (auto &tt : TP) {
				for (auto &x : GP[tt]) {
					TT.push_back(x);
				}
			}
			return MakeAns(TT, Remaining(TT));
		}
	}
	vector<int>res(n);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < p.size(); i++) {
              ~~^~~~~~~~~~
split.cpp:148:13: warning: unused variable 't' [-Wunused-variable]
  for (auto &t : T[mid]) {
             ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36