oj.uz

Submission #211830

# Submission time Handle Problem Language Result Execution time Memory
211830 2020-03-21T13:36:33 Z MarcoMeijer Split the Attractions (IOI19_split) C++14
40 / 100
 275 ms 55640 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 = 3e5;
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 26 ms 35584 KB ok, correct split
2 Correct 25 ms 35584 KB ok, correct split
3 Correct 27 ms 35584 KB ok, correct split
4 Correct 26 ms 35584 KB ok, correct split
5 Correct 26 ms 35584 KB ok, correct split
6 Correct 25 ms 35584 KB ok, correct split
7 Correct 186 ms 55288 KB ok, correct split
8 Correct 183 ms 53756 KB ok, correct split
9 Correct 182 ms 52856 KB ok, correct split
10 Correct 178 ms 55520 KB ok, correct split
11 Correct 183 ms 55640 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35584 KB ok, correct split
2 Correct 26 ms 35584 KB ok, correct split
3 Correct 26 ms 35584 KB ok, correct split
4 Correct 215 ms 52984 KB ok, correct split
5 Correct 170 ms 47992 KB ok, correct split
6 Correct 183 ms 55544 KB ok, correct split
7 Correct 192 ms 53240 KB ok, correct split
8 Correct 232 ms 51704 KB ok, correct split
9 Correct 180 ms 49528 KB ok, correct split
10 Correct 107 ms 46960 KB ok, correct split
11 Correct 112 ms 46960 KB ok, correct split
12 Correct 118 ms 47344 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35584 KB ok, correct split
2 Correct 171 ms 47992 KB ok, correct split
3 Correct 72 ms 40568 KB ok, correct split
4 Correct 36 ms 35560 KB ok, correct split
5 Correct 275 ms 51368 KB ok, correct split
6 Correct 198 ms 51192 KB ok, correct split
7 Correct 174 ms 51192 KB ok, correct split
8 Correct 234 ms 52088 KB ok, correct split
9 Correct 187 ms 51192 KB ok, correct split
10 Correct 66 ms 39672 KB ok, no valid answer
11 Correct 85 ms 41720 KB ok, no valid answer
12 Correct 153 ms 47604 KB ok, no valid answer
13 Correct 188 ms 47992 KB ok, no valid answer
14 Correct 112 ms 47396 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB ok, correct split
2 Correct 27 ms 35584 KB ok, no valid answer
3 Correct 25 ms 35584 KB ok, correct split
4 Correct 27 ms 35576 KB ok, correct split
5 Correct 27 ms 35584 KB ok, correct split
6 Correct 35 ms 35584 KB ok, correct split
7 Correct 27 ms 35584 KB ok, correct split
8 Correct 27 ms 35584 KB ok, correct split
9 Correct 29 ms 35968 KB ok, correct split
10 Correct 29 ms 35968 KB ok, correct split
11 Correct 26 ms 35584 KB ok, correct split
12 Correct 29 ms 35964 KB ok, correct split
13 Correct 26 ms 35576 KB ok, correct split
14 Correct 27 ms 35584 KB ok, correct split
15 Correct 26 ms 35584 KB ok, correct split
16 Correct 26 ms 35584 KB ok, correct split
17 Correct 25 ms 35584 KB ok, correct split
18 Incorrect 25 ms 35584 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 26 ms 35584 KB ok, correct split
2 Correct 25 ms 35584 KB ok, correct split
3 Correct 27 ms 35584 KB ok, correct split
4 Correct 26 ms 35584 KB ok, correct split
5 Correct 26 ms 35584 KB ok, correct split
6 Correct 25 ms 35584 KB ok, correct split
7 Correct 186 ms 55288 KB ok, correct split
8 Correct 183 ms 53756 KB ok, correct split
9 Correct 182 ms 52856 KB ok, correct split
10 Correct 178 ms 55520 KB ok, correct split
11 Correct 183 ms 55640 KB ok, correct split
12 Correct 26 ms 35584 KB ok, correct split
13 Correct 26 ms 35584 KB ok, correct split
14 Correct 26 ms 35584 KB ok, correct split
15 Correct 215 ms 52984 KB ok, correct split
16 Correct 170 ms 47992 KB ok, correct split
17 Correct 183 ms 55544 KB ok, correct split
18 Correct 192 ms 53240 KB ok, correct split
19 Correct 232 ms 51704 KB ok, correct split
20 Correct 180 ms 49528 KB ok, correct split
21 Correct 107 ms 46960 KB ok, correct split
22 Correct 112 ms 46960 KB ok, correct split
23 Correct 118 ms 47344 KB ok, correct split
24 Correct 26 ms 35584 KB ok, correct split
25 Correct 171 ms 47992 KB ok, correct split
26 Correct 72 ms 40568 KB ok, correct split
27 Correct 36 ms 35560 KB ok, correct split
28 Correct 275 ms 51368 KB ok, correct split
29 Correct 198 ms 51192 KB ok, correct split
30 Correct 174 ms 51192 KB ok, correct split
31 Correct 234 ms 52088 KB ok, correct split
32 Correct 187 ms 51192 KB ok, correct split
33 Correct 66 ms 39672 KB ok, no valid answer
34 Correct 85 ms 41720 KB ok, no valid answer
35 Correct 153 ms 47604 KB ok, no valid answer
36 Correct 188 ms 47992 KB ok, no valid answer
37 Correct 112 ms 47396 KB ok, no valid answer
38 Correct 27 ms 35584 KB ok, correct split
39 Correct 27 ms 35584 KB ok, no valid answer
40 Correct 25 ms 35584 KB ok, correct split
41 Correct 27 ms 35576 KB ok, correct split
42 Correct 27 ms 35584 KB ok, correct split
43 Correct 35 ms 35584 KB ok, correct split
44 Correct 27 ms 35584 KB ok, correct split
45 Correct 27 ms 35584 KB ok, correct split
46 Correct 29 ms 35968 KB ok, correct split
47 Correct 29 ms 35968 KB ok, correct split
48 Correct 26 ms 35584 KB ok, correct split
49 Correct 29 ms 35964 KB ok, correct split
50 Correct 26 ms 35576 KB ok, correct split
51 Correct 27 ms 35584 KB ok, correct split
52 Correct 26 ms 35584 KB ok, correct split
53 Correct 26 ms 35584 KB ok, correct split
54 Correct 25 ms 35584 KB ok, correct split
55 Incorrect 25 ms 35584 KB invalid split: #1=18, #2=23, #3=16
56 Halted 0 ms 0 KB -