oj.uz

Submission #296498

# Submission time Handle Problem Language Result Execution time Memory
296498 2020-09-10T15:25:26 Z b00n0rp Split the Attractions (IOI19_split) C++17
40 / 100
 181 ms 28536 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
 
const int MX = 200005;
 
vi g[MX],adj[MX];
int par[MX],dep[MX],sz[MX];
pii A[MX];
 
bitset<MX> vis;
 
vi ans;
 
void dfs(int u,int p,int d = 0){
	par[u] = p;
	vis[u] = 1;
	dep[u] = d;
	sz[u] = 1;
	for(auto v:g[u]){
		if(vis[v]) continue;
		adj[u].pb(v);
		adj[v].pb(u);
		dfs(v,u,d-1);
		sz[u] += sz[v];
	}
}

void assign(int u,int val){
	vis[u] = 1;
	if(A[val].F){
		ans[u] = A[val].S;
		A[val].F--;
	}
	else ans[u] = A[2].S;
	for(auto v:adj[u]){
		if(!vis[v]) assign(v,val);
	}
}
 
vi find_split(int n, int a, int b, int c, vi p, vi q) {
	A[0] = {a,1};
	A[1] = {b,2};
	A[2] = {c,3};
	sort(A,A+3);
	ans.resize(n);
	REP(i,(int)p.size()){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	dfs(0,0);
	vis.reset();
	REP(i,n){
		if(sz[i] >= A[0].F and n-sz[i] >= A[0].F){
			vis[i] = 1;
			if(sz[i] < n-sz[i]){
				assign(par[i],1);
				assign(i,0);
			}
			else{
				assign(par[i],0);
				assign(i,1);
			}
			return ans;
		}
	}
	return vi(n,0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 141 ms 26936 KB ok, correct split
8 Correct 143 ms 24696 KB ok, correct split
9 Correct 138 ms 24056 KB ok, correct split
10 Correct 139 ms 28536 KB ok, correct split
11 Correct 147 ms 28536 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 168 ms 25976 KB ok, correct split
5 Correct 125 ms 20856 KB ok, correct split
6 Correct 141 ms 28536 KB ok, correct split
7 Correct 139 ms 25720 KB ok, correct split
8 Correct 181 ms 23800 KB ok, correct split
9 Correct 127 ms 20728 KB ok, correct split
10 Correct 89 ms 21108 KB ok, correct split
11 Correct 86 ms 21104 KB ok, correct split
12 Correct 90 ms 21488 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 120 ms 19808 KB ok, correct split
3 Correct 41 ms 14200 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 133 ms 23288 KB ok, correct split
6 Correct 132 ms 23032 KB ok, correct split
7 Correct 137 ms 22924 KB ok, correct split
8 Correct 130 ms 24188 KB ok, correct split
9 Correct 123 ms 22648 KB ok, correct split
10 Correct 34 ms 13432 KB ok, no valid answer
11 Correct 52 ms 15268 KB ok, no valid answer
12 Correct 96 ms 21236 KB ok, no valid answer
13 Correct 117 ms 20984 KB ok, no valid answer
14 Correct 89 ms 21488 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, no valid answer
3 Correct 6 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 7 ms 9728 KB ok, correct split
8 Correct 7 ms 9728 KB ok, correct split
9 Correct 9 ms 10112 KB ok, correct split
10 Correct 9 ms 9984 KB ok, correct split
11 Correct 8 ms 9728 KB ok, correct split
12 Correct 9 ms 10112 KB ok, correct split
13 Correct 6 ms 9728 KB ok, correct split
14 Correct 7 ms 9728 KB ok, correct split
15 Correct 7 ms 9728 KB ok, correct split
16 Correct 7 ms 9728 KB ok, correct split
17 Correct 7 ms 9728 KB ok, correct split
18 Correct 7 ms 9728 KB ok, correct split
19 Correct 7 ms 9856 KB ok, correct split
20 Correct 8 ms 9856 KB ok, correct split
21 Correct 9 ms 10112 KB ok, correct split
22 Correct 9 ms 10112 KB ok, correct split
23 Correct 9 ms 10112 KB ok, correct split
24 Correct 8 ms 10112 KB ok, correct split
25 Correct 9 ms 10112 KB ok, correct split
26 Incorrect 9 ms 10112 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 141 ms 26936 KB ok, correct split
8 Correct 143 ms 24696 KB ok, correct split
9 Correct 138 ms 24056 KB ok, correct split
10 Correct 139 ms 28536 KB ok, correct split
11 Correct 147 ms 28536 KB ok, correct split
12 Correct 7 ms 9728 KB ok, correct split
13 Correct 7 ms 9728 KB ok, correct split
14 Correct 7 ms 9728 KB ok, correct split
15 Correct 168 ms 25976 KB ok, correct split
16 Correct 125 ms 20856 KB ok, correct split
17 Correct 141 ms 28536 KB ok, correct split
18 Correct 139 ms 25720 KB ok, correct split
19 Correct 181 ms 23800 KB ok, correct split
20 Correct 127 ms 20728 KB ok, correct split
21 Correct 89 ms 21108 KB ok, correct split
22 Correct 86 ms 21104 KB ok, correct split
23 Correct 90 ms 21488 KB ok, correct split
24 Correct 7 ms 9728 KB ok, correct split
25 Correct 120 ms 19808 KB ok, correct split
26 Correct 41 ms 14200 KB ok, correct split
27 Correct 7 ms 9728 KB ok, correct split
28 Correct 133 ms 23288 KB ok, correct split
29 Correct 132 ms 23032 KB ok, correct split
30 Correct 137 ms 22924 KB ok, correct split
31 Correct 130 ms 24188 KB ok, correct split
32 Correct 123 ms 22648 KB ok, correct split
33 Correct 34 ms 13432 KB ok, no valid answer
34 Correct 52 ms 15268 KB ok, no valid answer
35 Correct 96 ms 21236 KB ok, no valid answer
36 Correct 117 ms 20984 KB ok, no valid answer
37 Correct 89 ms 21488 KB ok, no valid answer
38 Correct 7 ms 9728 KB ok, correct split
39 Correct 7 ms 9728 KB ok, no valid answer
40 Correct 6 ms 9728 KB ok, correct split
41 Correct 7 ms 9728 KB ok, correct split
42 Correct 7 ms 9728 KB ok, correct split
43 Correct 7 ms 9728 KB ok, correct split
44 Correct 7 ms 9728 KB ok, correct split
45 Correct 7 ms 9728 KB ok, correct split
46 Correct 9 ms 10112 KB ok, correct split
47 Correct 9 ms 9984 KB ok, correct split
48 Correct 8 ms 9728 KB ok, correct split
49 Correct 9 ms 10112 KB ok, correct split
50 Correct 6 ms 9728 KB ok, correct split
51 Correct 7 ms 9728 KB ok, correct split
52 Correct 7 ms 9728 KB ok, correct split
53 Correct 7 ms 9728 KB ok, correct split
54 Correct 7 ms 9728 KB ok, correct split
55 Correct 7 ms 9728 KB ok, correct split
56 Correct 7 ms 9856 KB ok, correct split
57 Correct 8 ms 9856 KB ok, correct split
58 Correct 9 ms 10112 KB ok, correct split
59 Correct 9 ms 10112 KB ok, correct split
60 Correct 9 ms 10112 KB ok, correct split
61 Correct 8 ms 10112 KB ok, correct split
62 Correct 9 ms 10112 KB ok, correct split
63 Incorrect 9 ms 10112 KB jury found a solution, contestant did not
64 Halted 0 ms 0 KB -