oj.uz

Submission #211834

# Submission time Handle Problem Language Result Execution time Memory
211834 2020-03-21T13:43:38 Z MarcoMeijer Split the Attractions (IOI19_split) C++14
33 / 100
 218 ms 66168 KB 
#include <bits/stdc++.h>
using namespace std;

//macros
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
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX = 4e5;
int n, m, a[3], SA[3], r;
vi adj[MX], chl[MX], tAdj[MX];
bitset<MX> visited;
int sz[MX];
int cent;
int subN[MX];
set<int> subAdj[MX];
set<int> curSub;
int curSubSz;
vi ans;

void dfsChl(int u=r) {
	visited[u] = 1;
	for(int v:adj[u]) {
		if(visited[v]) continue;
		dfsChl(v);
		chl[u].pb(v);
		tAdj[u].pb(v);
		tAdj[v].pb(u);
	}
}
void dfsSize(int u=r) {
	sz[u] = 1;
	for(int v:chl[u]) {
		dfsSize(v);
		sz[u] += sz[v];
	}
}
int getCentroid(int u=r) {
	for(int v:chl[u])
		if(sz[v] > n/2)
			return getCentroid(v);
	return u;
}
void dfsChl2(int u) {
	visited[u] = 1;
	for(int v:tAdj[u]) if(!visited[v]) dfsChl2(v), chl[u].pb(v);
}
void dfsSubNumb(int u, int s) {
	subN[u] = s;
	for(int v:chl[u]) dfsSubNumb(v, s);
}
void dfsSubSize(int u) {
	if(visited[u]) return;
	visited[u] = 1;
	if(curSubSz >= a[SA[0]]) return;
	curSubSz += sz[u];
	curSub.insert(u);
	for(int v:subAdj[u]) {
		dfsSubSize(v);
		if(curSubSz >= a[SA[0]]) return;
	}
}
void dfsAns1(int u) {
	if(!curSub.count(subN[u])) return;
	if(visited[u]) return;
	if(a[SA[0]]==0) return;
	visited[u] = 1;
	a[SA[0]]--;
	ans[u] = 0;
	for(int v:adj[u]) dfsAns1(v);
}
void dfsAns2(int u) {
	if(curSub.count(subN[u])) return;
	if(visited[u]) return;
	if(a[SA[1]]==0) return;
	visited[u] = 1;
	a[SA[1]]--;
	ans[u] = 1;
	for(int v:adj[u]) dfsAns2(v);
}
vi find_split(int N, int A, int B, int C, vi p, vi q) {
	r=rng()%N;
	n=N; m=p.size();
	a[0] = A;
	a[1] = B;
	a[2] = C;
	RE(i,3) SA[i]=i;
	sort(SA,SA+3,[](int i, int j) {return a[i]<a[j];});
	RE(i,m) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	visited.reset();
	dfsChl();
	dfsSize();
	cent = getCentroid();
	RE(i,n) chl[i].clear();
	visited.reset();
	dfsChl2(cent);
	dfsSize(cent);
	for(int v:chl[cent]) dfsSubNumb(v, v);
	RE(u,n) {
		if(u == cent) continue;
		for(int v:adj[u]) if(subN[u] != subN[v]) {
			if(v == cent) continue;
			subAdj[subN[u]].insert(subN[v]);
			subAdj[subN[v]].insert(subN[u]);
		}
	}
	visited.reset();
	for(int v:chl[cent]) {
		if(visited[v]) continue;
		curSubSz = 0;
		curSub.clear();
		dfsSubSize(v);
		if(curSubSz >= a[SA[0]]) break;
		curSub.clear();
	}
	ans.resize(n);
	if(curSub.empty()) {
		RE(i,n) ans[i] = 0;
	} else {
		RE(i,n) ans[i] = 2;
		visited.reset();
		dfsAns1(*curSub.begin());
		dfsAns2(cent);
		RE(i,n) ans[i] = SA[ans[i]]+1;
	}
	return ans;
}

Subtask #1
0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47360 KB ok, correct split
2 Correct 29 ms 47360 KB ok, correct split
3 Correct 28 ms 47360 KB ok, correct split
4 Correct 200 ms 62840 KB ok, correct split
5 Correct 156 ms 58616 KB ok, correct split
6 Correct 175 ms 66168 KB ok, correct split
7 Correct 172 ms 64120 KB ok, correct split
8 Correct 216 ms 61176 KB ok, correct split
9 Correct 179 ms 60024 KB ok, correct split
10 Correct 109 ms 57968 KB ok, correct split
11 Correct 104 ms 57968 KB ok, correct split
12 Correct 106 ms 57968 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47360 KB ok, correct split
2 Correct 158 ms 58616 KB ok, correct split
3 Correct 71 ms 51832 KB ok, correct split
4 Correct 29 ms 47360 KB ok, correct split
5 Correct 197 ms 62840 KB ok, correct split
6 Correct 170 ms 62840 KB ok, correct split
7 Correct 218 ms 62328 KB ok, correct split
8 Correct 179 ms 62884 KB ok, correct split
9 Correct 174 ms 62072 KB ok, correct split
10 Correct 61 ms 51064 KB ok, no valid answer
11 Correct 86 ms 52984 KB ok, no valid answer
12 Correct 128 ms 58228 KB ok, no valid answer
13 Correct 182 ms 58488 KB ok, no valid answer
14 Correct 121 ms 57968 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47360 KB ok, correct split
2 Correct 33 ms 47360 KB ok, no valid answer
3 Correct 29 ms 47360 KB ok, correct split
4 Correct 29 ms 47360 KB ok, correct split
5 Correct 30 ms 47360 KB ok, correct split
6 Incorrect 30 ms 47360 KB invalid split: #1=3, #2=0, #3=13
7 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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