oj.uz

Submission #817633

# Submission time Handle Problem Language Result Execution time Memory
817633 2023-08-09T14:18:57 Z welleyth Split the Attractions (IOI19_split) C++17
18 / 100
 65 ms 17692 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = (int)3e5;

vector<int> g[N];
int sz[N];
bool used[N];
int p[N];
mt19937 rnd(time(nullptr));

void dfs (int v){
	sz[v] = 1;
	used[v] = true;
	for(auto& to : g[v]){
		if(used[to]) continue;
		p[to] = v;
		dfs(to);
		sz[v] += sz[to];
	}
	return;
};

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	bool group1 = true;
	int m = p.size();
	for(int i = 0; i < m; i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	for(int i = 0; i < n; i++){
		group1 &= (g[i].size() <= 2);
	}
	if(group1){
		int root = 0;
		for(int i = 0; i < n; i++){
			if(g[i].size() == 1)
				root = i;
		}
		queue<int> q;
		q.push(root);
		bool used[n];
		memset(used,0,sizeof used);
		vector<int> order;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			used[v] = true;
			order.push_back(v);
			for(auto& to : g[v]){
				if(!used[to]){
					used[to] = true;
					q.push(to);
				}
			}
		}
		vector<int> ans(n);
		for(int i = 0; i < a; i++){
			ans[order[i]] = 1;
		}
		for(int i = a; i < a+b; i++){
			ans[order[i]] = 2;
		}
		for(int i = a+b; i < a+b+c; i++){
			ans[order[i]] = 3;
		}
		return ans;
	}
	if(a == 1){
		bool used[n];
		memset(used,0,sizeof used);
		bool deleted = false;
		vector<int> ans(n);
		for(int i = 0; i < n; i++){
			if(g[i].size() == 1){
				deleted = true;
				used[i] = true;
				ans[i] = 1;
				break;
			}
		}
		if(!deleted){
			used[0] = true;
			ans[0] = 1;
			deleted = true;
		}
		int root = 0;
		if(used[root]) root++;
		queue<int> q;
		q.push(root);
		vector<int> order;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			used[v] = true;
			order.push_back(v);
			for(auto& to : g[v]){
				if(!used[to]){
					used[to] = true;
					q.push(to);
				}
			}
		}
		for(int i = 0; i < b; i++){
			ans[order[i]] = 2;
		}
		for(int i = b; i < b+c; i++){
			ans[order[i]] = 3;
		}
		return ans;
	}
	if(m == n-1){
		int val[3] = {1,2,3};
		if(a > b){
			swap(a,b);
			swap(val[0],val[1]);
		}
		if(b > c){
			swap(b,c);
			swap(val[1],val[2]);
		}
		if(a > b){
			swap(a,b);
			swap(val[0],val[1]);
		}
		memset(used,0,sizeof used);
		memset(sz,0,sizeof sz);
		int root = 0;
		for(int i = 0; i < n; i++){
			if(g[i].size() > 1)
				root = i;
		}
		// root = rnd()%n;
		p[root] = -1;
		dfs(root);
		memset(used,0,sizeof used);
		vector<int> ans(n,0);
		for(int i = 0; i < n; i++){
			if(sz[i] >= a && n - sz[i] >= b){
				queue<int> q;
				q.push(i);
				used[i] = true;
				ans[i] = val[0];
				a--;
				while(!q.empty() && a > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[0];
					for(auto& to : g[v]){
						if(to == p[v]) continue;
						q.push(to);
						a--;
					}
				}
				q.push(p[i]);
				used[p[i]] = true;
				ans[p[i]] = val[1];
				b--;
				while(!q.empty() && b > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[1];
					for(auto& to : g[v]){
						if(used[to]) continue;
						q.push(to);
						b--;
					}
				}
				for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
				return ans;
			}
			if(sz[i] >= b && n - sz[i] >= a){
				queue<int> q;
				q.push(i);
				used[i] = true;
				ans[i] = val[1];
				b--;
				while(!q.empty() && b > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[1];
					for(auto& to : g[v]){
						if(to == p[v]) continue;
						q.push(to);
						b--;
					}
				}
				q.push(p[i]);
				used[p[i]] = true;
				ans[p[i]] = val[0];
				a--;
				while(!q.empty() && a > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[0];
					for(auto& to : g[v]){
						if(used[to]) continue;
						q.push(to);
						a--;
					}
				}
				for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
				return ans;
			}
		}
		return ans;
	}
	return vector<int>(n,0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB ok, correct split
2 Correct 4 ms 7352 KB ok, correct split
3 Correct 3 ms 7252 KB ok, correct split
4 Correct 4 ms 7356 KB ok, correct split
5 Correct 4 ms 7252 KB ok, correct split
6 Correct 4 ms 7252 KB ok, correct split
7 Correct 41 ms 13400 KB ok, correct split
8 Correct 39 ms 14152 KB ok, correct split
9 Correct 39 ms 14152 KB ok, correct split
10 Correct 39 ms 14104 KB ok, correct split
11 Correct 58 ms 14088 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB ok, correct split
2 Correct 3 ms 7252 KB ok, correct split
3 Correct 3 ms 7252 KB ok, correct split
4 Correct 51 ms 16052 KB ok, correct split
5 Correct 39 ms 14444 KB ok, correct split
6 Correct 38 ms 14152 KB ok, correct split
7 Correct 44 ms 14152 KB ok, correct split
8 Correct 65 ms 17692 KB ok, correct split
9 Correct 41 ms 14224 KB ok, correct split
10 Correct 36 ms 14844 KB ok, correct split
11 Correct 33 ms 14776 KB ok, correct split
12 Correct 38 ms 15160 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB ok, correct split
2 Correct 4 ms 7352 KB ok, correct split
3 Correct 3 ms 7252 KB ok, correct split
4 Correct 4 ms 7356 KB ok, correct split
5 Correct 4 ms 7252 KB ok, correct split
6 Correct 4 ms 7252 KB ok, correct split
7 Correct 41 ms 13400 KB ok, correct split
8 Correct 39 ms 14152 KB ok, correct split
9 Correct 39 ms 14152 KB ok, correct split
10 Correct 39 ms 14104 KB ok, correct split
11 Correct 58 ms 14088 KB ok, correct split
12 Correct 3 ms 7252 KB ok, correct split
13 Correct 3 ms 7252 KB ok, correct split
14 Correct 3 ms 7252 KB ok, correct split
15 Correct 51 ms 16052 KB ok, correct split
16 Correct 39 ms 14444 KB ok, correct split
17 Correct 38 ms 14152 KB ok, correct split
18 Correct 44 ms 14152 KB ok, correct split
19 Correct 65 ms 17692 KB ok, correct split
20 Correct 41 ms 14224 KB ok, correct split
21 Correct 36 ms 14844 KB ok, correct split
22 Correct 33 ms 14776 KB ok, correct split
23 Correct 38 ms 15160 KB ok, correct split
24 Incorrect 4 ms 8764 KB invalid split: #1=2, #2=0, #3=3
25 Halted 0 ms 0 KB -