oj.uz

Submission #143964

# Submission time Handle Problem Language Result Execution time Memory
143964 2019-08-15T13:50:36 Z sasa Split the Attractions (IOI19_split) C++14
22 / 100
 258 ms 35456 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;
	}
	if(root != 0){
		memset(mark, 0, sizeof mark);
		for(int i=0; i<n; i++)
			tree[i].clear(), oth[i].clear();
		dfs(root);
	}
	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
0 / 7.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 20 ms 20088 KB ok, correct split
4 Correct 20 ms 20088 KB ok, correct split
5 Correct 21 ms 20088 KB ok, correct split
6 Incorrect 20 ms 20088 KB invalid split: #1=1, #2=20, #3=79
7 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 20 ms 20088 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20088 KB ok, correct split
2 Correct 217 ms 31336 KB ok, correct split
3 Correct 90 ms 24568 KB ok, correct split
4 Correct 20 ms 20088 KB ok, correct split
5 Correct 258 ms 34660 KB ok, correct split
6 Correct 245 ms 34448 KB ok, correct split
7 Correct 240 ms 34424 KB ok, correct split
8 Correct 254 ms 35456 KB ok, correct split
9 Correct 246 ms 34428 KB ok, correct split
10 Correct 65 ms 23652 KB ok, no valid answer
11 Correct 94 ms 25452 KB ok, no valid answer
12 Correct 169 ms 30572 KB ok, no valid answer
13 Correct 207 ms 30936 KB ok, no valid answer
14 Correct 147 ms 30224 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20140 KB ok, correct split
2 Correct 20 ms 20088 KB ok, no valid answer
3 Correct 21 ms 20132 KB ok, correct split
4 Correct 20 ms 20088 KB ok, correct split
5 Incorrect 20 ms 20084 KB invalid split: #1=11, #2=4, #3=1
6 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 20088 KB ok, correct split
3 Correct 20 ms 20088 KB ok, correct split
4 Correct 20 ms 20088 KB ok, correct split
5 Correct 21 ms 20088 KB ok, correct split
6 Incorrect 20 ms 20088 KB invalid split: #1=1, #2=20, #3=79
7 Halted 0 ms 0 KB -