oj.uz

Submission #211833

# Submission time Handle Problem Language Result Execution time Memory
211833 2020-03-21T13:41:23 Z MarcoMeijer Split the Attractions (IOI19_split) C++14
40 / 100
 242 ms 66172 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]]) 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) {
	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47360 KB ok, correct split
2 Correct 32 ms 47360 KB ok, correct split
3 Correct 32 ms 47360 KB ok, correct split
4 Correct 29 ms 47360 KB ok, correct split
5 Correct 25 ms 47360 KB ok, correct split
6 Correct 31 ms 47360 KB ok, correct split
7 Correct 201 ms 65024 KB ok, correct split
8 Correct 173 ms 63864 KB ok, correct split
9 Correct 194 ms 63512 KB ok, correct split
10 Correct 183 ms 66168 KB ok, correct split
11 Correct 207 ms 66172 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 32 ms 47360 KB ok, correct split
3 Correct 31 ms 47356 KB ok, correct split
4 Correct 242 ms 62840 KB ok, correct split
5 Correct 158 ms 58616 KB ok, correct split
6 Correct 208 ms 66168 KB ok, correct split
7 Correct 185 ms 64760 KB ok, correct split
8 Correct 228 ms 61176 KB ok, correct split
9 Correct 184 ms 59896 KB ok, correct split
10 Correct 110 ms 57968 KB ok, correct split
11 Correct 104 ms 57968 KB ok, correct split
12 Correct 112 ms 57968 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47360 KB ok, correct split
2 Correct 184 ms 58616 KB ok, correct split
3 Correct 80 ms 51960 KB ok, correct split
4 Correct 30 ms 47360 KB ok, correct split
5 Correct 212 ms 61792 KB ok, correct split
6 Correct 199 ms 62200 KB ok, correct split
7 Correct 200 ms 62840 KB ok, correct split
8 Correct 193 ms 62456 KB ok, correct split
9 Correct 187 ms 61944 KB ok, correct split
10 Correct 65 ms 51064 KB ok, no valid answer
11 Correct 88 ms 52984 KB ok, no valid answer
12 Correct 137 ms 58228 KB ok, no valid answer
13 Correct 165 ms 58488 KB ok, no valid answer
14 Correct 124 ms 57968 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47360 KB ok, correct split
2 Correct 30 ms 47360 KB ok, no valid answer
3 Correct 31 ms 47360 KB ok, correct split
4 Correct 29 ms 47360 KB ok, correct split
5 Correct 34 ms 47356 KB ok, correct split
6 Correct 31 ms 47360 KB ok, correct split
7 Correct 31 ms 47352 KB ok, correct split
8 Correct 33 ms 47360 KB ok, correct split
9 Correct 38 ms 47744 KB ok, correct split
10 Correct 37 ms 47864 KB ok, correct split
11 Correct 32 ms 47360 KB ok, correct split
12 Correct 36 ms 47744 KB ok, correct split
13 Correct 31 ms 47360 KB ok, correct split
14 Correct 31 ms 47360 KB ok, correct split
15 Correct 34 ms 47360 KB ok, correct split
16 Correct 32 ms 47352 KB ok, correct split
17 Correct 33 ms 47360 KB ok, correct split
18 Correct 32 ms 47360 KB ok, correct split
19 Correct 31 ms 47480 KB ok, correct split
20 Correct 35 ms 47488 KB ok, correct split
21 Correct 35 ms 47712 KB ok, correct split
22 Correct 32 ms 47872 KB ok, correct split
23 Correct 33 ms 47744 KB ok, correct split
24 Correct 35 ms 47732 KB ok, correct split
25 Correct 34 ms 47736 KB ok, correct split
26 Incorrect 45 ms 47992 KB invalid split: #1=800, #2=0, #3=1600
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47360 KB ok, correct split
2 Correct 32 ms 47360 KB ok, correct split
3 Correct 32 ms 47360 KB ok, correct split
4 Correct 29 ms 47360 KB ok, correct split
5 Correct 25 ms 47360 KB ok, correct split
6 Correct 31 ms 47360 KB ok, correct split
7 Correct 201 ms 65024 KB ok, correct split
8 Correct 173 ms 63864 KB ok, correct split
9 Correct 194 ms 63512 KB ok, correct split
10 Correct 183 ms 66168 KB ok, correct split
11 Correct 207 ms 66172 KB ok, correct split
12 Correct 30 ms 47360 KB ok, correct split
13 Correct 32 ms 47360 KB ok, correct split
14 Correct 31 ms 47356 KB ok, correct split
15 Correct 242 ms 62840 KB ok, correct split
16 Correct 158 ms 58616 KB ok, correct split
17 Correct 208 ms 66168 KB ok, correct split
18 Correct 185 ms 64760 KB ok, correct split
19 Correct 228 ms 61176 KB ok, correct split
20 Correct 184 ms 59896 KB ok, correct split
21 Correct 110 ms 57968 KB ok, correct split
22 Correct 104 ms 57968 KB ok, correct split
23 Correct 112 ms 57968 KB ok, correct split
24 Correct 30 ms 47360 KB ok, correct split
25 Correct 184 ms 58616 KB ok, correct split
26 Correct 80 ms 51960 KB ok, correct split
27 Correct 30 ms 47360 KB ok, correct split
28 Correct 212 ms 61792 KB ok, correct split
29 Correct 199 ms 62200 KB ok, correct split
30 Correct 200 ms 62840 KB ok, correct split
31 Correct 193 ms 62456 KB ok, correct split
32 Correct 187 ms 61944 KB ok, correct split
33 Correct 65 ms 51064 KB ok, no valid answer
34 Correct 88 ms 52984 KB ok, no valid answer
35 Correct 137 ms 58228 KB ok, no valid answer
36 Correct 165 ms 58488 KB ok, no valid answer
37 Correct 124 ms 57968 KB ok, no valid answer
38 Correct 30 ms 47360 KB ok, correct split
39 Correct 30 ms 47360 KB ok, no valid answer
40 Correct 31 ms 47360 KB ok, correct split
41 Correct 29 ms 47360 KB ok, correct split
42 Correct 34 ms 47356 KB ok, correct split
43 Correct 31 ms 47360 KB ok, correct split
44 Correct 31 ms 47352 KB ok, correct split
45 Correct 33 ms 47360 KB ok, correct split
46 Correct 38 ms 47744 KB ok, correct split
47 Correct 37 ms 47864 KB ok, correct split
48 Correct 32 ms 47360 KB ok, correct split
49 Correct 36 ms 47744 KB ok, correct split
50 Correct 31 ms 47360 KB ok, correct split
51 Correct 31 ms 47360 KB ok, correct split
52 Correct 34 ms 47360 KB ok, correct split
53 Correct 32 ms 47352 KB ok, correct split
54 Correct 33 ms 47360 KB ok, correct split
55 Correct 32 ms 47360 KB ok, correct split
56 Correct 31 ms 47480 KB ok, correct split
57 Correct 35 ms 47488 KB ok, correct split
58 Correct 35 ms 47712 KB ok, correct split
59 Correct 32 ms 47872 KB ok, correct split
60 Correct 33 ms 47744 KB ok, correct split
61 Correct 35 ms 47732 KB ok, correct split
62 Correct 34 ms 47736 KB ok, correct split
63 Incorrect 45 ms 47992 KB invalid split: #1=800, #2=0, #3=1600
64 Halted 0 ms 0 KB -