oj.uz

Submission #986879

# Submission time Handle Problem Language Result Execution time Memory
986879 2024-05-21T13:43:36 Z PagodePaiva Split the Attractions (IOI19_split) C++17
29 / 100
 607 ms 1048576 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n;
vector <int> g[N];
int sz[N];
int pai[N];
int res[N];
vector <int> tipos = {1, 2, 3};

void dfs(int v, int p){
	sz[v] = 1;
	pai[v] = p;
	for(auto x : g[v]){
		if(x == p) continue;
		dfs(x, v);
		sz[v] += sz[x];
	}
	return;
}

void dfs2(int v, int p, int& tam, int typ){
	if(tam == 0) return;
	res[v] = typ;
	tam--;
	for(auto x : g[v]){
		if(x == p) continue;
		dfs2(x, v, tam, typ);
	} 
	return;
}
void solve(int v, int a, int b){
	int p = pai[v];
	dfs2(v, pai[v], a, tipos[0]);
	dfs2(pai[v], v, b, tipos[1]);
	for(int i = 1;i <= n;i++){
		if(res[i] == 0) res[i] = tipos[2];
	}
	return;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	if(a > b) {
		swap(a, b);
		swap(tipos[0], tipos[1]);
	}
	if(a > c){
		swap(a, c);
		swap(tipos[0], tipos[2]);
	} 
	if(b > c) {
		swap(b, c);
		swap(tipos[1], tipos[2]);
	}
	for(int i = 1;i < n;i++){
		g[p[i-1]+1].push_back(q[i-1]+1);
		g[q[i-1]+1].push_back(p[i-1]+1);
	}
	dfs(1, 1);
	for(int i = 1;i <= n;i++){
		if(sz[i] >= a and n-sz[i] >= b){
			solve(i, a, b);
			vector <int> ans;
			for(int i = 1;i <= n;i++) ans.push_back(res[i]);
			return ans;
		}
		else if(sz[i] >= b and n-sz[i] >= a){
			swap(tipos[0], tipos[1]);
			solve(i, b, a);
			vector <int> ans;
			for(int i = 1;i <= n;i++) ans.push_back(res[i]);
			return ans;
		}
	}
	vector <int> ans;
	for(int i = 1;i <= n;i++) ans.push_back(0);
	return ans;
}

Compilation message

split.cpp: In function 'void solve(int, int, int)':
split.cpp:35:6: warning: unused variable 'p' [-Wunused-variable]
   35 |  int p = pai[v];
      |      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Correct 1 ms 3676 KB ok, correct split
5 Correct 1 ms 3624 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 48 ms 17748 KB ok, correct split
8 Correct 44 ms 15584 KB ok, correct split
9 Correct 43 ms 14892 KB ok, correct split
10 Correct 42 ms 17872 KB ok, correct split
11 Correct 48 ms 16700 KB ok, correct split

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 38 ms 10460 KB ok, correct split
3 Correct 15 ms 6620 KB ok, correct split
4 Correct 2 ms 3788 KB ok, correct split
5 Correct 44 ms 13016 KB ok, correct split
6 Correct 42 ms 12724 KB ok, correct split
7 Correct 46 ms 12372 KB ok, correct split
8 Correct 46 ms 13792 KB ok, correct split
9 Correct 50 ms 12312 KB ok, correct split
10 Correct 13 ms 5980 KB ok, no valid answer
11 Correct 19 ms 7004 KB ok, no valid answer
12 Correct 35 ms 10680 KB ok, no valid answer
13 Correct 38 ms 10196 KB ok, no valid answer
14 Correct 36 ms 10708 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB ok, correct split
2 Correct 1 ms 3676 KB ok, correct split
3 Correct 1 ms 3676 KB ok, correct split
4 Correct 1 ms 3676 KB ok, correct split
5 Correct 1 ms 3624 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 48 ms 17748 KB ok, correct split
8 Correct 44 ms 15584 KB ok, correct split
9 Correct 43 ms 14892 KB ok, correct split
10 Correct 42 ms 17872 KB ok, correct split
11 Correct 48 ms 16700 KB ok, correct split
12 Correct 1 ms 3676 KB ok, correct split
13 Correct 1 ms 3928 KB ok, correct split
14 Incorrect 1 ms 3672 KB invalid split: #1=0, #2=1, #3=4
15 Halted 0 ms 0 KB -