oj.uz

Submission #295037

# Submission time Handle Problem Language Result Execution time Memory
295037 2020-09-09T12:46:52 Z Atill83 Split the Attractions (IOI19_split) C++14
11 / 100
 144 ms 21240 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 + 1;
	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 + 1;
	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] + 1;
		}
	}else{
		dfs5(0, 0);
	}

	return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB ok, correct split
2 Correct 7 ms 7424 KB ok, correct split
3 Correct 5 ms 7424 KB ok, correct split
4 Correct 5 ms 7424 KB ok, correct split
5 Correct 5 ms 7424 KB ok, correct split
6 Correct 5 ms 7424 KB ok, correct split
7 Incorrect 128 ms 21240 KB invalid split: #1=66667, #2=0, #3=33333
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.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 7 ms 7424 KB ok, correct split
4 Correct 101 ms 13944 KB ok, correct split
5 Correct 88 ms 13176 KB ok, correct split
6 Correct 80 ms 12792 KB ok, correct split
7 Correct 85 ms 14456 KB ok, correct split
8 Correct 144 ms 15352 KB ok, correct split
9 Correct 86 ms 12920 KB ok, correct split
10 Correct 61 ms 13296 KB ok, correct split
11 Correct 64 ms 13296 KB ok, correct split
12 Correct 65 ms 13320 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7424 KB 2 components are not connected
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=4, #2=3, #3=2
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB ok, correct split
2 Correct 7 ms 7424 KB ok, correct split
3 Correct 5 ms 7424 KB ok, correct split
4 Correct 5 ms 7424 KB ok, correct split
5 Correct 5 ms 7424 KB ok, correct split
6 Correct 5 ms 7424 KB ok, correct split
7 Incorrect 128 ms 21240 KB invalid split: #1=66667, #2=0, #3=33333
8 Halted 0 ms 0 KB -