oj.uz

Submission #296560

# Submission time Handle Problem Language Result Execution time Memory
296560 2020-09-10T16:17:41 Z b00n0rp Split the Attractions (IOI19_split) C++17
18 / 100
 713 ms 1048580 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 n,m,par[MX],dep[MX],sz[MX],root;
pii A[MX];
 
bitset<MX> vis;
 
vi ans;

int comp;
int dsusz[2*MX],dsupar[2*MX];
 
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);
	}
}

void assign_graph(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:g[u]){
		if(!vis[v]) assign_graph(v,val);
	}
}
 
void dsubuild(int u,int c){
	dsupar[u] = c;
	vis[u] = 1;
	for(auto v:adj[u]){
		if(!vis[v]) dsubuild(v,c);
	}
}

int findpar(int x){
	if(dsupar[x] == x) return x;
	return dsupar[x] = findpar(dsupar[x]);
}

vi find_split(int n, int a, int b, int c, vi p, vi q) {
	::n = n;
	m = p.size();
	A[0] = {a,1};
	A[1] = {b,2};
	A[2] = {c,3};
	sort(A,A+3);
	ans.resize(n);
	REP(i,m){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}

	REP(i,n) adj[i].clear();
	vis.reset();
	root = 0;
	dfs(root,root);

	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;
		}
	}
	REP(i,n){
		int mx = n-sz[i];
		for(auto v:adj[i]){
			if(v != par[i]){
				mx = max(mx,sz[v]);
			}
		}
		if(mx >= a) continue;
		comp = n;
		vis.reset();
		vis[i] = 1;
		for(auto v:adj[i]){
			if(v == par[i]) dsusz[comp] = n-sz[i];
			else dsusz[comp] = sz[v];
			dsubuild(v,comp);
		}
		vis.reset();
		int head = -1;
		REP(j,m){
			if(p[j] == i or q[j] == i) continue;
			int u = findpar(p[j]);
			int v = findpar(q[j]);
			if(u == v) continue;
			if(dsusz[u] > dsusz[v]) swap(u,v);
			dsusz[v] += dsusz[u];
			dsupar[u] = v;
			if(dsusz[v] >= A[0].F){
				head = v;
				break;
			}
		}
		if(head == -1) return vi(n,0);
		vi v1,v2;
		REP(j,n){
			if(j == i or findpar(j) != head) v2.pb(j);
			else v1.pb(j);
		}
		if(dsusz[head] >= A[1].F){
			vis.reset();
			for(auto x:v1) vis[x] = 1;
			assign_graph(v1[0],1);
			vis.reset();
			for(auto x:v2) vis[x] = 1;
			assign_graph(v2[0],0);
		}
		else{
			vis.reset();
			for(auto x:v1) vis[x] = 1;
			assign_graph(v1[0],0);
			vis.reset();
			for(auto x:v2) vis[x] = 1;
			assign_graph(v2[0],1);
		}
		return ans;
	}
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:167:1: warning: control reaches end of non-void function [-Wreturn-type]
  167 | }
      | ^

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 127 ms 27000 KB ok, correct split
8 Correct 130 ms 24696 KB ok, correct split
9 Correct 133 ms 24128 KB ok, correct split
10 Correct 158 ms 27384 KB ok, correct split
11 Correct 129 ms 27384 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 6 ms 9728 KB ok, correct split
3 Correct 7 ms 9760 KB ok, correct split
4 Correct 163 ms 24184 KB ok, correct split
5 Correct 126 ms 19832 KB ok, correct split
6 Correct 140 ms 27384 KB ok, correct split
7 Correct 136 ms 24568 KB ok, correct split
8 Correct 173 ms 21624 KB ok, correct split
9 Correct 123 ms 19576 KB ok, correct split
10 Correct 85 ms 20336 KB ok, correct split
11 Correct 90 ms 20336 KB ok, correct split
12 Correct 91 ms 20336 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 113 ms 19704 KB ok, correct split
3 Correct 41 ms 13816 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 134 ms 22148 KB ok, correct split
6 Correct 131 ms 21880 KB ok, correct split
7 Correct 129 ms 21788 KB ok, correct split
8 Correct 125 ms 23032 KB ok, correct split
9 Correct 131 ms 21500 KB ok, correct split
10 Runtime error 713 ms 1048580 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

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 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 7 ms 9728 KB ok, correct split
8 Correct 7 ms 9728 KB ok, correct split
9 Correct 10 ms 10112 KB ok, correct split
10 Correct 9 ms 10112 KB ok, correct split
11 Correct 7 ms 9728 KB ok, correct split
12 Correct 10 ms 10112 KB ok, correct split
13 Correct 8 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 10 ms 10104 KB ok, correct split
22 Correct 9 ms 10112 KB ok, correct split
23 Correct 9 ms 10112 KB ok, correct split
24 Correct 9 ms 10112 KB ok, correct split
25 Correct 9 ms 10112 KB ok, correct split
26 Runtime error 680 ms 1048576 KB Execution killed with signal 9
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 127 ms 27000 KB ok, correct split
8 Correct 130 ms 24696 KB ok, correct split
9 Correct 133 ms 24128 KB ok, correct split
10 Correct 158 ms 27384 KB ok, correct split
11 Correct 129 ms 27384 KB ok, correct split
12 Correct 7 ms 9728 KB ok, correct split
13 Correct 6 ms 9728 KB ok, correct split
14 Correct 7 ms 9760 KB ok, correct split
15 Correct 163 ms 24184 KB ok, correct split
16 Correct 126 ms 19832 KB ok, correct split
17 Correct 140 ms 27384 KB ok, correct split
18 Correct 136 ms 24568 KB ok, correct split
19 Correct 173 ms 21624 KB ok, correct split
20 Correct 123 ms 19576 KB ok, correct split
21 Correct 85 ms 20336 KB ok, correct split
22 Correct 90 ms 20336 KB ok, correct split
23 Correct 91 ms 20336 KB ok, correct split
24 Correct 7 ms 9728 KB ok, correct split
25 Correct 113 ms 19704 KB ok, correct split
26 Correct 41 ms 13816 KB ok, correct split
27 Correct 7 ms 9728 KB ok, correct split
28 Correct 134 ms 22148 KB ok, correct split
29 Correct 131 ms 21880 KB ok, correct split
30 Correct 129 ms 21788 KB ok, correct split
31 Correct 125 ms 23032 KB ok, correct split
32 Correct 131 ms 21500 KB ok, correct split
33 Runtime error 713 ms 1048580 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -