oj.uz

Submission #143971

# Submission time Handle Problem Language Result Execution time Memory
143971 2019-08-15T14:03:54 Z sasa Split the Attractions (IOI19_split) C++14
29 / 100
 260 ms 39248 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);
			tree[u].push_back(v);
			dfs(u);
		}
		else{
			oth[u].push_back(v);
			oth[v].push_back(u);
		}
	}
}
bool markTree[maxn];
void dfs_tree(int v,int root){
	sz[v] = 1;
	if(v == root)
		memset(markTree, 0, sizeof markTree);
	if(markTree[v])
		return;
	markTree[v] = 1;
	for(auto u : tree[v]){
		if(markTree[u])
			continue;
		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 && sz[u] < sz[root])
				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 20344 KB ok, correct split
2 Correct 20 ms 20344 KB ok, correct split
3 Correct 20 ms 20216 KB ok, correct split
4 Correct 20 ms 20344 KB ok, correct split
5 Correct 20 ms 20344 KB ok, correct split
6 Correct 21 ms 20344 KB ok, correct split
7 Correct 238 ms 38776 KB ok, correct split
8 Correct 211 ms 36984 KB ok, correct split
9 Correct 226 ms 36344 KB ok, correct split
10 Correct 237 ms 39248 KB ok, correct split
11 Correct 248 ms 39212 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20216 KB ok, correct split
2 Correct 20 ms 20344 KB ok, correct split
3 Incorrect 20 ms 20224 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 20220 KB ok, correct split
2 Correct 189 ms 33148 KB ok, correct split
3 Correct 72 ms 25592 KB ok, correct split
4 Correct 20 ms 20320 KB ok, correct split
5 Correct 225 ms 35020 KB ok, correct split
6 Correct 260 ms 34808 KB ok, correct split
7 Correct 226 ms 34680 KB ok, correct split
8 Correct 232 ms 35704 KB ok, correct split
9 Correct 231 ms 34808 KB ok, correct split
10 Correct 62 ms 24440 KB ok, no valid answer
11 Correct 85 ms 26488 KB ok, no valid answer
12 Correct 167 ms 33268 KB ok, no valid answer
13 Correct 200 ms 32868 KB ok, no valid answer
14 Correct 147 ms 33648 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20216 KB ok, correct split
2 Correct 22 ms 20216 KB ok, no valid answer
3 Correct 20 ms 20216 KB ok, correct split
4 Correct 20 ms 20344 KB ok, correct split
5 Correct 21 ms 20344 KB ok, correct split
6 Correct 21 ms 20216 KB ok, correct split
7 Correct 21 ms 20344 KB ok, correct split
8 Correct 20 ms 20320 KB ok, correct split
9 Correct 24 ms 20728 KB ok, correct split
10 Correct 24 ms 20728 KB ok, correct split
11 Correct 21 ms 20216 KB ok, correct split
12 Correct 25 ms 20728 KB ok, correct split
13 Correct 20 ms 20344 KB ok, correct split
14 Correct 21 ms 20316 KB ok, correct split
15 Correct 21 ms 20216 KB ok, correct split
16 Correct 20 ms 20344 KB ok, correct split
17 Correct 20 ms 20220 KB ok, correct split
18 Correct 24 ms 20344 KB ok, correct split
19 Correct 21 ms 20344 KB ok, correct split
20 Correct 22 ms 20472 KB ok, correct split
21 Correct 23 ms 20600 KB ok, correct split
22 Correct 23 ms 20600 KB ok, correct split
23 Correct 23 ms 20728 KB ok, correct split
24 Correct 23 ms 20600 KB ok, correct split
25 Correct 22 ms 20600 KB ok, correct split
26 Incorrect 23 ms 20856 KB invalid split: #1=800, #2=1, #3=1599
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20344 KB ok, correct split
2 Correct 20 ms 20344 KB ok, correct split
3 Correct 20 ms 20216 KB ok, correct split
4 Correct 20 ms 20344 KB ok, correct split
5 Correct 20 ms 20344 KB ok, correct split
6 Correct 21 ms 20344 KB ok, correct split
7 Correct 238 ms 38776 KB ok, correct split
8 Correct 211 ms 36984 KB ok, correct split
9 Correct 226 ms 36344 KB ok, correct split
10 Correct 237 ms 39248 KB ok, correct split
11 Correct 248 ms 39212 KB ok, correct split
12 Correct 20 ms 20216 KB ok, correct split
13 Correct 20 ms 20344 KB ok, correct split
14 Incorrect 20 ms 20224 KB invalid split: #1=1, #2=1, #3=3
15 Halted 0 ms 0 KB -