oj.uz

Submission #352595

# Submission time Handle Problem Language Result Execution time Memory
352595 2021-01-21T02:35:26 Z tengiz05 Split the Attractions (IOI19_split) C++17
18 / 100
 193 ms 25836 KB 
#include "split.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
int n, m;
vector<int> edges[N];
vector<int> g[N];
bool used[N];
int subtree_size[N];
vector<pii> extra;
void Dfs(int u, int p=-1){
	used[u] = true;
	subtree_size[u] = 1;
	for(auto v : edges[u]){
		if(used[v]){
			if(v != p)extra.pb({u,v});
			continue;
		}
		g[u].pb(v);
		g[v].pb(u);
		Dfs(v,u);
		subtree_size[u] += subtree_size[v];
	}
}
int find_centroid(int u, int p){
	for(auto v : g[u]){
		if(v!=p && subtree_size[v] > n/2)return find_centroid(v,u);
	}return u;
}
void recalc_size(int u, int p){
	subtree_size[u] = 1;
	for(auto v : g[u]){
		if(v == p)continue;
		recalc_size(v,u);
		subtree_size[u] += subtree_size[v];
	}
}

// start of DSU
vector<int> p, sz;
void Init(int n){
	p.assign(n,0);
	sz.assign(n,1);
	for(int i=0;i<n;i++)p[i]=i;
}
int par(int u){
	if(p[u] == u)return u;
	return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
	return par(u) == par(v);
}
void merge(int u,int v){
	u=par(u);v=par(v);
	if(u == v)return;
	p[v] = u;
	sz[u] += sz[v];
	return;
}
int size_of_node(int u){
	return sz[par(u)];
}// end of DSU

pii sizes[3];
vector<int> ans;
int center;
int remaining;
void color(int u){
	used[u] = true;
	ans[u] = sizes[0].second;
	remaining--;
	if(not remaining)return;
	for(auto v : g[u]){
		if(not remaining)return;
		if(used[v] || v == center)continue;
		color(v);
	}
}

void colorB(int u){
	used[u] = true;
	ans[u] = sizes[1].second;
	remaining--;
	if(not remaining)return;
	for(auto v : edges[u]){
		if(not remaining)return;
		if(used[v])continue;
		colorB(v);
	}
}


vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> Q) {
	Init(N);
	sizes[0] = {a,1};
	sizes[1] = {b,2};
	sizes[2] = {c,3};
	sort(sizes,sizes+3);
	a = sizes[0].first;
	b = sizes[1].first;
	c = sizes[2].first;
	n=N; m = P.size();
	for(int i=0;i<m;i++){
		edges[P[i]].pb(Q[i]);
		edges[Q[i]].pb(P[i]);
	}
	ans.assign(n,sizes[2].second);
	Dfs(0);
	center = find_centroid(0,0);
	recalc_size(center,center);
	for(int u=1;u<n;u++){
		for(auto v : g[u]){
			if(v != center)merge(u,v);
		}
	}for(auto u : edges[center]){
		if(size_of_node(u) >= a){
			// yay we found solution! (I hope)
			remaining = a;
			memset(used,0,sizeof used);
			color(u);
			remaining = b;
			colorB(center);
			return ans;
		}
	}
	for(auto [u, v] : extra){
		if(IsSame(u,v))continue;
		g[u].pb(v);
		g[v].pb(u);
		merge(u,v);
		for(auto u : edges[center]){
			if(size_of_node(u) >= a){
				// yay we found solution! (I hope)
				remaining = a;
				memset(used,0,sizeof used);
				color(u);
				assert(not remaining);
				remaining = b;
				colorB(center);
				assert(not remaining);
				return ans;
			}
		}
	}
	return vector<int>(n,0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB ok, correct split
2 Correct 4 ms 5100 KB ok, correct split
3 Correct 4 ms 5100 KB ok, correct split
4 Correct 4 ms 5100 KB ok, correct split
5 Correct 4 ms 5120 KB ok, correct split
6 Correct 4 ms 5100 KB ok, correct split
7 Correct 149 ms 25324 KB ok, correct split
8 Correct 143 ms 22104 KB ok, correct split
9 Correct 150 ms 21228 KB ok, correct split
10 Correct 139 ms 25836 KB ok, correct split
11 Correct 163 ms 25836 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB ok, correct split
2 Correct 4 ms 5228 KB ok, correct split
3 Correct 4 ms 5100 KB ok, correct split
4 Correct 193 ms 21724 KB ok, correct split
5 Correct 122 ms 15084 KB ok, correct split
6 Correct 137 ms 25836 KB ok, correct split
7 Correct 142 ms 21940 KB ok, correct split
8 Correct 178 ms 18404 KB ok, correct split
9 Correct 131 ms 15084 KB ok, correct split
10 Correct 76 ms 15716 KB ok, correct split
11 Correct 82 ms 15716 KB ok, correct split
12 Correct 88 ms 15716 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB ok, correct split
2 Incorrect 130 ms 15084 KB invalid split: #1=613, #2=40000, #3=59387
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB ok, correct split
2 Correct 4 ms 4972 KB ok, no valid answer
3 Correct 4 ms 5248 KB ok, correct split
4 Correct 4 ms 5100 KB ok, correct split
5 Correct 4 ms 5100 KB ok, correct split
6 Correct 4 ms 5100 KB ok, correct split
7 Correct 4 ms 5100 KB ok, correct split
8 Correct 4 ms 5100 KB ok, correct split
9 Correct 7 ms 5612 KB ok, correct split
10 Correct 6 ms 5484 KB ok, correct split
11 Correct 4 ms 5100 KB ok, correct split
12 Incorrect 6 ms 5484 KB invalid split: #1=1, #2=1600, #3=800
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB ok, correct split
2 Correct 4 ms 5100 KB ok, correct split
3 Correct 4 ms 5100 KB ok, correct split
4 Correct 4 ms 5100 KB ok, correct split
5 Correct 4 ms 5120 KB ok, correct split
6 Correct 4 ms 5100 KB ok, correct split
7 Correct 149 ms 25324 KB ok, correct split
8 Correct 143 ms 22104 KB ok, correct split
9 Correct 150 ms 21228 KB ok, correct split
10 Correct 139 ms 25836 KB ok, correct split
11 Correct 163 ms 25836 KB ok, correct split
12 Correct 4 ms 5100 KB ok, correct split
13 Correct 4 ms 5228 KB ok, correct split
14 Correct 4 ms 5100 KB ok, correct split
15 Correct 193 ms 21724 KB ok, correct split
16 Correct 122 ms 15084 KB ok, correct split
17 Correct 137 ms 25836 KB ok, correct split
18 Correct 142 ms 21940 KB ok, correct split
19 Correct 178 ms 18404 KB ok, correct split
20 Correct 131 ms 15084 KB ok, correct split
21 Correct 76 ms 15716 KB ok, correct split
22 Correct 82 ms 15716 KB ok, correct split
23 Correct 88 ms 15716 KB ok, correct split
24 Correct 4 ms 5100 KB ok, correct split
25 Incorrect 130 ms 15084 KB invalid split: #1=613, #2=40000, #3=59387
26 Halted 0 ms 0 KB -