Submission #211835

#	Time	Username	Problem	Language	Result	Execution time	Memory
211835		MarcoMeijer	Split the Attractions (IOI19_split)	C++14	0 / 100	12 ms	14464 KiB

split

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second

const int MX=3e5, MOD=1e9+7;
int n, m, a[4], root=0;
int rsa[4], sa[4], val[4];
vi p, q;
vi chl[MX], adj[MX];
int sz[MX], parent[MX], split=-1;
vi ans;
bitset<MX> visited, p1;
int p1Size=0;

void dfsChl(int u=0, int p=-1) {
	if(visited[u]) return;
	visited[u] = 1;
	parent[u] = p;
	if(p != -1) chl[p].pb(u);
	for(int v:adj[u])
		dfsChl(v, u);
}
int dfsSz(int u=0) {
	sz[u] = 1;
	for(int v:chl[u])
		sz[u] += dfsSz(v);
	return sz[u];
}
void dfsSplit(int u=0) {
	int mxSz=0;
	for(int v:chl[u]) mxSz=max(mxSz, sz[v]);
	if(sz[u] >= a[1] && mxSz < a[1])
		split = u;
	for(int v:chl[u])
		dfsSplit(v);
}
void dfsP1(int u) {
	p1[u]=1;
	for(int v:chl[u])
		dfsP1(v);
}
void dfsP1Rev(int u) {
	p1[u]=0;
	for(int v:chl[u])
		dfsP1Rev(v);
}
bool dfsP2(int u) {
	bool conp2=0;
	for(int v:adj[u])
		if(!p1[v])
			conp2=1;
	if(conp2) {
		if(p1Size - sz[u] < a[1]) {
			return 1;
		} else {
			p1Size -= sz[u];
			dfsP1Rev(u);
		}
	} else {
		for(int v:chl[u])
			if(dfsP2(v))
				return 1;
	}
	return 0;
}
void dfsFillAns(int u, bool g, int c) {
	if(p1[u] != g) return;
	if(visited[u]) return;
	visited[u] = 1;
	if(a[c] != 0)
		ans[u] = c, a[c]--;
	for(int v:adj[u])
		dfsFillAns(v, g, c);
}
void find_split_5() {
	visited.reset();
	dfsChl();
	dfsSz();
	dfsSplit();
	p1.reset();
	dfsP1(split);
	p1Size = sz[split];
	for(int v:chl[split]) {
		if(dfsP2(v)) {
			dfsFillAns(split, 1, 1);
			dfsFillAns(parent[split], 0, 2);
			return;
		}
	}
	if(n - p1Size < a[1]) {
		//not possible
		RE(i,n) ans[i] = 0;
	} else {
		dfsFillAns(split, 1, 1);
		dfsFillAns(parent[split], 0, 2);
	}
}
vi find_split(int N, int A, int B, int C, vi P, vi Q) {
	val[1]=A, val[2]=B, val[3]=C;
	RE1(i,3) sa[i]=i;
	sort(sa+1, sa+4, [](int i, int j) {
		return val[i]<val[j];
	});
	RE1(i,3) rsa[sa[i]] = i; rsa[0] = 0;
	n=N, p=P, q=Q;
	RE1(i,3) a[i] = val[sa[i]];
	m = p.size();
	ans.assign(n, 3);

	RE(i,m) adj[p[i]].pb(q[i]), adj[q[i]].pb(p[i]);

	find_split_5();

	RE(i,n) ans[i] = rsa[ans[i]];
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:11:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define REP(a,b,c) for(int a=int(b); a<int(c); a++)
                    ^
split.cpp:13:18: note: in expansion of macro 'REP'
 #define RE1(a,c) REP(a,1,c+1)
                  ^~~
split.cpp:120:2: note: in expansion of macro 'RE1'
  RE1(i,3) rsa[sa[i]] = i; rsa[0] = 0;
  ^~~
split.cpp:120:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  RE1(i,3) rsa[sa[i]] = i; rsa[0] = 0;
                           ^~~

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