oj.uz

Submission #143950

# Submission time Handle Problem Language Result Execution time Memory
143950 2019-08-15T13:31:58 Z sasa Split the Attractions (IOI19_split) C++14
18 / 100
 255 ms 39160 KB 
#include "split.h"
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 10;
vi adj[maxn], tree[maxn], oth[maxn];
vi g[maxn];

int num[3], ans[maxn], sz[maxn], comp[maxn];
bool mark[maxn];
void dfs(int v){
	mark[v] = 1;
	for(auto u : adj[v]){
		if(!mark[u]){
			tree[v].push_back(u);
			dfs(u);
		}
		else{
			oth[u].push_back(v);
			oth[v].push_back(u);
		}
	}
}
void dfs_tree(int v,int root){
	sz[v] = 1;
	for(auto u : tree[v]){
		if(v == root)
			comp[u] = u;
		else
			comp[u] = comp[v];
		dfs_tree(u, root);
		sz[v] += sz[u];
	}
}
int Rem;
void dfs_g(int v){
	if(mark[v])
		return;
	mark[v] = 1;
	Rem -= sz[v];
	if(Rem <= 0) return;
	for(auto u : g[v])
		dfs_g(u);

}
int answer[maxn];
int rems = 0;
void dfs_ok(int v,int col){
	if(mark[v] || ans[v] != col || rems <= 0)
		return;
	rems--;
	answer[v] = col;
	mark[v] = 1;
	for(auto u : adj[v])
		dfs_ok(u, col);
}
void make_ok(int n){
	for(int i=0; i<n; i++)
		answer[i] = 3;
	rems = num[0];
	memset(mark, 0, sizeof mark);
	for(int i=0; i<n; i++)
		if(ans[i] == 1){
			dfs_ok(i, 1);
			break;
		}
	rems = num[1];
	memset(mark, 0, sizeof mark);
	for(int i=0; i<n; i++)
		if(ans[i] == 2){
			dfs_ok(i, 2);
			break;
		}
}
vector<int> find_split(int n, int a1, int b1, int c1, vector<int> from, vector<int> to) {
	int m = from.size();
	num[0] = a1, num[1] = b1, num[2] = c1;
	sort(num, num + 3);
	
	for(int i=0; i<m; i++){
		int u = from[i], v = to[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	dfs_tree(0, 0);
	int root = 0;
	while(1){
		int bef = root;
		for(auto u : tree[root]){
			if(sz[u] > n/2)
				root = u;
		}
		if(bef == root)
			break;
	}
	memset(sz, 0, sizeof sz);
	dfs_tree(root, root);
	bool can = true;
	if(m == n - 1){
		can = false;
		for(auto u : tree[root]){
			if(sz[u] >= num[0]){
				for(int i=0; i<n; i++)
					ans[i] = (comp[i] == u ? 1 : 2);
				can = true;
				break;
			}
		}
		make_ok(n);
	}
	else{
		for(int i=0; i<n; i++){
			ans[i] = 2;
			for(auto j : oth[i]){
				if(j != root && i != root){
					int u = comp[i];
					int v = comp[j];
					if(u != v){
						g[u].push_back(v);
						g[v].push_back(u);
					}
				}
			}
		}
		can = false;
		for(auto u : tree[root]){
			if(sz[u] >= num[0]){
				for(int i=0; i<n; i++)
					ans[i] = (comp[i] == u ? 1 : 2);
				can = true;
				break;
			}
		}
		if(!can){
			Rem = num[0];
			memset(mark, 0, sizeof mark);
			for(auto u : tree[root])
				dfs_g(u);
			for(int i=0; i<n; i++){
				if(i != root && mark[comp[i]])
					ans[i] = 1;
				else
					ans[i] = 2;
			}
			can = true;
		}
		make_ok(n);
	}/*
	cout << "CAN" << can << endl;
	for(int i=0; i<n; i++)
		cout << answer[i] << " ";
	cout << endl;*/
	pii per[3];
	per[0] = {a1, 1};
	per[1] = {b1, 2};
	per[2] = {c1, 3};
	sort(per, per + 3);
	vi res;
	res.resize(n);
	if(can){
		for(int i=0; i<n; i++)
			res[i] = per[answer[i] - 1].Y;
	}
	return res;
}
/*
int main(){
	int n, m;
	cin >> n >> m;
	int a1, b1, c1;
	cin >> a1 >> b1 >> c1;
	vi fr, to;
	for(int i=0; i<m; i++){
		int x, y;
		cin >> x >> y;
		fr.push_back(x);
		to.push_back(y);
	}
	vi res = find_split(n, a1, b1, c1, fr, to);
	for(auto t : res)
		cout << t << " ";
	cout << endl;
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Correct 19 ms 20088 KB ok, correct split
3 Correct 19 ms 20088 KB ok, correct split
4 Correct 19 ms 20060 KB ok, correct split
5 Correct 20 ms 20088 KB ok, correct split
6 Correct 20 ms 20188 KB ok, correct split
7 Correct 222 ms 38592 KB ok, correct split
8 Correct 194 ms 36908 KB ok, correct split
9 Correct 200 ms 36176 KB ok, correct split
10 Correct 213 ms 38892 KB ok, correct split
11 Correct 214 ms 39160 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Correct 19 ms 20088 KB ok, correct split
3 Correct 19 ms 20180 KB ok, correct split
4 Correct 238 ms 37652 KB ok, correct split
5 Correct 162 ms 31352 KB ok, correct split
6 Correct 203 ms 39032 KB ok, correct split
7 Correct 211 ms 36720 KB ok, correct split
8 Correct 255 ms 35448 KB ok, correct split
9 Correct 195 ms 32680 KB ok, correct split
10 Correct 115 ms 30620 KB ok, correct split
11 Correct 118 ms 30704 KB ok, correct split
12 Correct 125 ms 30704 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Incorrect 162 ms 30972 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Correct 19 ms 20088 KB ok, no valid answer
3 Correct 20 ms 20088 KB ok, correct split
4 Correct 20 ms 20088 KB ok, correct split
5 Correct 20 ms 20088 KB ok, correct split
6 Correct 20 ms 20088 KB ok, correct split
7 Correct 20 ms 20088 KB ok, correct split
8 Correct 20 ms 20088 KB ok, correct split
9 Correct 23 ms 20472 KB ok, correct split
10 Correct 23 ms 20472 KB ok, correct split
11 Correct 20 ms 20216 KB ok, correct split
12 Correct 23 ms 20600 KB ok, correct split
13 Correct 19 ms 20088 KB ok, correct split
14 Correct 19 ms 20088 KB ok, correct split
15 Correct 19 ms 20088 KB ok, correct split
16 Correct 19 ms 20088 KB ok, correct split
17 Correct 19 ms 20088 KB ok, correct split
18 Incorrect 20 ms 20088 KB invalid split: #1=1, #2=40, #3=16
19 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Correct 19 ms 20088 KB ok, correct split
3 Correct 19 ms 20088 KB ok, correct split
4 Correct 19 ms 20060 KB ok, correct split
5 Correct 20 ms 20088 KB ok, correct split
6 Correct 20 ms 20188 KB ok, correct split
7 Correct 222 ms 38592 KB ok, correct split
8 Correct 194 ms 36908 KB ok, correct split
9 Correct 200 ms 36176 KB ok, correct split
10 Correct 213 ms 38892 KB ok, correct split
11 Correct 214 ms 39160 KB ok, correct split
12 Correct 20 ms 20088 KB ok, correct split
13 Correct 19 ms 20088 KB ok, correct split
14 Correct 19 ms 20180 KB ok, correct split
15 Correct 238 ms 37652 KB ok, correct split
16 Correct 162 ms 31352 KB ok, correct split
17 Correct 203 ms 39032 KB ok, correct split
18 Correct 211 ms 36720 KB ok, correct split
19 Correct 255 ms 35448 KB ok, correct split
20 Correct 195 ms 32680 KB ok, correct split
21 Correct 115 ms 30620 KB ok, correct split
22 Correct 118 ms 30704 KB ok, correct split
23 Correct 125 ms 30704 KB ok, correct split
24 Correct 20 ms 20088 KB ok, correct split
25 Incorrect 162 ms 30972 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -