oj.uz

Submission #143959

# Submission time Handle Problem Language Result Execution time Memory
143959 2019-08-15T13:43:39 Z sasa Split the Attractions (IOI19_split) C++14
18 / 100
 321 ms 39004 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 20 ms 20052 KB ok, correct split
3 Correct 20 ms 20216 KB ok, correct split
4 Correct 20 ms 20060 KB ok, correct split
5 Correct 20 ms 20088 KB ok, correct split
6 Correct 20 ms 20088 KB ok, correct split
7 Correct 203 ms 38584 KB ok, correct split
8 Correct 187 ms 36728 KB ok, correct split
9 Correct 198 ms 36216 KB ok, correct split
10 Correct 207 ms 38900 KB ok, correct split
11 Correct 201 ms 38944 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 20 ms 20088 KB ok, correct split
3 Correct 19 ms 20088 KB ok, correct split
4 Correct 245 ms 37596 KB ok, correct split
5 Correct 168 ms 31452 KB ok, correct split
6 Correct 195 ms 39004 KB ok, correct split
7 Correct 196 ms 36600 KB ok, correct split
8 Correct 321 ms 35480 KB ok, correct split
9 Correct 181 ms 32696 KB ok, correct split
10 Correct 113 ms 30704 KB ok, correct split
11 Correct 132 ms 30704 KB ok, correct split
12 Correct 118 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 163 ms 30968 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 20 ms 20088 KB ok, no valid answer
3 Correct 20 ms 20088 KB ok, correct split
4 Correct 24 ms 20088 KB ok, correct split
5 Correct 24 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 20216 KB ok, correct split
9 Correct 24 ms 20600 KB ok, correct split
10 Correct 24 ms 20472 KB ok, correct split
11 Correct 20 ms 20088 KB ok, correct split
12 Correct 24 ms 20476 KB ok, correct split
13 Correct 20 ms 20088 KB ok, correct split
14 Correct 20 ms 20088 KB ok, correct split
15 Correct 20 ms 20088 KB ok, correct split
16 Correct 20 ms 20088 KB ok, correct split
17 Correct 20 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 20 ms 20052 KB ok, correct split
3 Correct 20 ms 20216 KB ok, correct split
4 Correct 20 ms 20060 KB ok, correct split
5 Correct 20 ms 20088 KB ok, correct split
6 Correct 20 ms 20088 KB ok, correct split
7 Correct 203 ms 38584 KB ok, correct split
8 Correct 187 ms 36728 KB ok, correct split
9 Correct 198 ms 36216 KB ok, correct split
10 Correct 207 ms 38900 KB ok, correct split
11 Correct 201 ms 38944 KB ok, correct split
12 Correct 20 ms 20088 KB ok, correct split
13 Correct 20 ms 20088 KB ok, correct split
14 Correct 19 ms 20088 KB ok, correct split
15 Correct 245 ms 37596 KB ok, correct split
16 Correct 168 ms 31452 KB ok, correct split
17 Correct 195 ms 39004 KB ok, correct split
18 Correct 196 ms 36600 KB ok, correct split
19 Correct 321 ms 35480 KB ok, correct split
20 Correct 181 ms 32696 KB ok, correct split
21 Correct 113 ms 30704 KB ok, correct split
22 Correct 132 ms 30704 KB ok, correct split
23 Correct 118 ms 30704 KB ok, correct split
24 Correct 20 ms 20088 KB ok, correct split
25 Incorrect 163 ms 30968 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -