oj.uz

Submission #211832

# Submission time Handle Problem Language Result Execution time Memory
211832 2020-03-21T13:37:56 Z MarcoMeijer Split the Attractions (IOI19_split) C++14
40 / 100
 224 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

const int MX = 4e5;
int n, m, a[3], SA[3];
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=0) {
	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=0) {
	sz[u] = 1;
	for(int v:chl[u]) {
		dfsSize(v);
		sz[u] += sz[v];
	}
}
int getCentroid(int u=0) {
	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]]) 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]]) 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) {
	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB ok, correct split
2 Correct 39 ms 47352 KB ok, correct split
3 Correct 36 ms 47224 KB ok, correct split
4 Correct 30 ms 47360 KB ok, correct split
5 Correct 30 ms 47360 KB ok, correct split
6 Correct 30 ms 47360 KB ok, correct split
7 Correct 178 ms 65784 KB ok, correct split
8 Correct 189 ms 64108 KB ok, correct split
9 Correct 178 ms 63480 KB ok, correct split
10 Correct 196 ms 66144 KB ok, correct split
11 Correct 177 ms 66168 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47360 KB ok, correct split
2 Correct 30 ms 47352 KB ok, correct split
3 Correct 30 ms 47360 KB ok, correct split
4 Correct 217 ms 62968 KB ok, correct split
5 Correct 182 ms 58620 KB ok, correct split
6 Correct 185 ms 66168 KB ok, correct split
7 Correct 178 ms 63864 KB ok, correct split
8 Correct 224 ms 61176 KB ok, correct split
9 Correct 180 ms 60024 KB ok, correct split
10 Correct 108 ms 57968 KB ok, correct split
11 Correct 108 ms 57972 KB ok, correct split
12 Correct 129 ms 57968 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB ok, correct split
2 Correct 163 ms 58616 KB ok, correct split
3 Correct 71 ms 51832 KB ok, correct split
4 Correct 30 ms 47360 KB ok, correct split
5 Correct 199 ms 62072 KB ok, correct split
6 Correct 177 ms 61688 KB ok, correct split
7 Correct 174 ms 61688 KB ok, correct split
8 Correct 183 ms 62860 KB ok, correct split
9 Correct 178 ms 61740 KB ok, correct split
10 Correct 62 ms 51064 KB ok, no valid answer
11 Correct 84 ms 52984 KB ok, no valid answer
12 Correct 134 ms 58228 KB ok, no valid answer
13 Correct 157 ms 58488 KB ok, no valid answer
14 Correct 112 ms 57968 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 47352 KB ok, correct split
2 Correct 31 ms 47352 KB ok, no valid answer
3 Correct 30 ms 47360 KB ok, correct split
4 Correct 31 ms 47360 KB ok, correct split
5 Correct 31 ms 47360 KB ok, correct split
6 Correct 31 ms 47360 KB ok, correct split
7 Correct 31 ms 47360 KB ok, correct split
8 Correct 30 ms 47360 KB ok, correct split
9 Correct 33 ms 47740 KB ok, correct split
10 Correct 33 ms 47736 KB ok, correct split
11 Correct 30 ms 47356 KB ok, correct split
12 Correct 32 ms 47744 KB ok, correct split
13 Correct 31 ms 47360 KB ok, correct split
14 Correct 30 ms 47308 KB ok, correct split
15 Correct 30 ms 47352 KB ok, correct split
16 Correct 30 ms 47360 KB ok, correct split
17 Correct 30 ms 47360 KB ok, correct split
18 Incorrect 30 ms 47404 KB invalid split: #1=18, #2=23, #3=16
19 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47360 KB ok, correct split
2 Correct 39 ms 47352 KB ok, correct split
3 Correct 36 ms 47224 KB ok, correct split
4 Correct 30 ms 47360 KB ok, correct split
5 Correct 30 ms 47360 KB ok, correct split
6 Correct 30 ms 47360 KB ok, correct split
7 Correct 178 ms 65784 KB ok, correct split
8 Correct 189 ms 64108 KB ok, correct split
9 Correct 178 ms 63480 KB ok, correct split
10 Correct 196 ms 66144 KB ok, correct split
11 Correct 177 ms 66168 KB ok, correct split
12 Correct 30 ms 47360 KB ok, correct split
13 Correct 30 ms 47352 KB ok, correct split
14 Correct 30 ms 47360 KB ok, correct split
15 Correct 217 ms 62968 KB ok, correct split
16 Correct 182 ms 58620 KB ok, correct split
17 Correct 185 ms 66168 KB ok, correct split
18 Correct 178 ms 63864 KB ok, correct split
19 Correct 224 ms 61176 KB ok, correct split
20 Correct 180 ms 60024 KB ok, correct split
21 Correct 108 ms 57968 KB ok, correct split
22 Correct 108 ms 57972 KB ok, correct split
23 Correct 129 ms 57968 KB ok, correct split
24 Correct 31 ms 47360 KB ok, correct split
25 Correct 163 ms 58616 KB ok, correct split
26 Correct 71 ms 51832 KB ok, correct split
27 Correct 30 ms 47360 KB ok, correct split
28 Correct 199 ms 62072 KB ok, correct split
29 Correct 177 ms 61688 KB ok, correct split
30 Correct 174 ms 61688 KB ok, correct split
31 Correct 183 ms 62860 KB ok, correct split
32 Correct 178 ms 61740 KB ok, correct split
33 Correct 62 ms 51064 KB ok, no valid answer
34 Correct 84 ms 52984 KB ok, no valid answer
35 Correct 134 ms 58228 KB ok, no valid answer
36 Correct 157 ms 58488 KB ok, no valid answer
37 Correct 112 ms 57968 KB ok, no valid answer
38 Correct 39 ms 47352 KB ok, correct split
39 Correct 31 ms 47352 KB ok, no valid answer
40 Correct 30 ms 47360 KB ok, correct split
41 Correct 31 ms 47360 KB ok, correct split
42 Correct 31 ms 47360 KB ok, correct split
43 Correct 31 ms 47360 KB ok, correct split
44 Correct 31 ms 47360 KB ok, correct split
45 Correct 30 ms 47360 KB ok, correct split
46 Correct 33 ms 47740 KB ok, correct split
47 Correct 33 ms 47736 KB ok, correct split
48 Correct 30 ms 47356 KB ok, correct split
49 Correct 32 ms 47744 KB ok, correct split
50 Correct 31 ms 47360 KB ok, correct split
51 Correct 30 ms 47308 KB ok, correct split
52 Correct 30 ms 47352 KB ok, correct split
53 Correct 30 ms 47360 KB ok, correct split
54 Correct 30 ms 47360 KB ok, correct split
55 Incorrect 30 ms 47404 KB invalid split: #1=18, #2=23, #3=16
56 Halted 0 ms 0 KB -