oj.uz

Submission #295031

# Submission time Handle Problem Language Result Execution time Memory
295031 2020-09-09T12:42:42 Z Atill83 Split the Attractions (IOI19_split) C++14
11 / 100
 132 ms 15748 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 3e5 + 5;
int N, m;
vector<int> res;
vector<int> adj[MAXN];
bool visited[MAXN];
int kal[3];
int sz[MAXN];
void dfs1(int v){
	visited[v] = 1;
	if(kal[1] == 0) return;
	res[v] = 2;
	kal[1]--;
	if(kal[1] == 0) return;
	for(int j: adj[v]){
		if(!visited[j]) 
			dfs1(j);
	}
}
int node = -1, st = -1;
void dfs2(int v, int par, int k1, int k2){
	sz[v] = 1;
	for(int j: adj[v]){
		if(j != par){
			dfs2(j, v, k1, k2);
			sz[v] += sz[j];
		}
	}
	int up = N - sz[v];

	if(up >= kal[k1] && sz[v] >= kal[k2]){
		node = v;
		st = 0;
	}else if(up >= kal[k2] && sz[v] >= kal[k1]){
		node = v;
		st = 1;
	}
}

void dfs4(int v, int par, int k){
	if(kal[k] == 0) return;
	res[v] = k;
	kal[k]--;
	if(kal[k] == 0) return;
	for(int j: adj[v]){
		if(j != par) dfs4(j, v, k);
	}
}


void dfs3(int v, int par, int k1, int k2){
	if(node == v){
		if(st == 0)
			dfs4(par, v, k1);
		else dfs4(par, v, k2);
		for(int j: adj[v]){
			if(st)
				dfs4(j, v, k1);
			else dfs4(j, v, k2);
		}
		return;
	}
	for(int j: adj[v]){
		if(j != par){
			dfs3(j, v, k1, k2);
		}
	}
}

void dfs5(int v, int sim){
	if(kal[sim] == 0) sim++;
	res[v] = sim;
	kal[sim]--;
	for(int j: adj[v]){
		if(!res[j]){
			dfs5(j, sim);
		}
	}
}



vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	res.resize(n, 0);
	m = p.size();
	for(int i = 0; i < m; i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	kal[0] = a;
	kal[1] = b;
	kal[2] = c;
	if(a == 1){
		dfs1(0);
		bool done = 0;
		for(int i = 0; i < n; i++){
			if(res[i]) continue;
			if(done) res[i] = 3;
			else{
				res[i] = 1;
				done = 1;
			}
		}
	}else if(m == n - 1){
		vector<int> ali = {0, 1, 2};
		sort(ali.begin(), ali.end(), [](int a, int b){
			return kal[a] < kal[b];
		});
		dfs2(0, -1, ali[0], ali[1]);
		if(node != -1){
			dfs3(0, -1, ali[0], ali[1]);
			for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = ali[2];
		}
	}else{
		dfs5(0, 0);
	}

	return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB ok, correct split
2 Correct 5 ms 7424 KB ok, correct split
3 Correct 5 ms 7424 KB ok, correct split
4 Incorrect 5 ms 7424 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB ok, correct split
2 Correct 5 ms 7424 KB ok, correct split
3 Correct 5 ms 7424 KB ok, correct split
4 Correct 109 ms 14456 KB ok, correct split
5 Correct 81 ms 13560 KB ok, correct split
6 Correct 80 ms 13560 KB ok, correct split
7 Correct 88 ms 14968 KB ok, correct split
8 Correct 132 ms 15748 KB ok, correct split
9 Correct 88 ms 13560 KB ok, correct split
10 Correct 62 ms 13808 KB ok, correct split
11 Correct 64 ms 13808 KB ok, correct split
12 Correct 64 ms 13808 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7424 KB invalid split: #1=1, #2=4, #3=0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7424 KB invalid split: #1=2, #2=7, #3=0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB ok, correct split
2 Correct 5 ms 7424 KB ok, correct split
3 Correct 5 ms 7424 KB ok, correct split
4 Incorrect 5 ms 7424 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -