oj.uz

Submission #986877

# Submission time Handle Problem Language Result Execution time Memory
986877 2024-05-21T13:41:21 Z PagodePaiva Split the Attractions (IOI19_split) C++17
7 / 100
 749 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){
			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 2 ms 3672 KB ok, correct split
4 Correct 2 ms 3788 KB ok, correct split
5 Correct 2 ms 3676 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 50 ms 17796 KB ok, correct split
8 Correct 43 ms 15576 KB ok, correct split
9 Correct 65 ms 14804 KB ok, correct split
10 Correct 42 ms 17884 KB ok, correct split
11 Correct 45 ms 16596 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 3676 KB ok, correct split
3 Incorrect 1 ms 3676 KB invalid split: #1=0, #2=1, #3=4
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB ok, correct split
2 Incorrect 44 ms 10368 KB invalid split: #1=40000, #2=20000, #3=40000
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 749 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 2 ms 3672 KB ok, correct split
4 Correct 2 ms 3788 KB ok, correct split
5 Correct 2 ms 3676 KB ok, correct split
6 Correct 1 ms 3676 KB ok, correct split
7 Correct 50 ms 17796 KB ok, correct split
8 Correct 43 ms 15576 KB ok, correct split
9 Correct 65 ms 14804 KB ok, correct split
10 Correct 42 ms 17884 KB ok, correct split
11 Correct 45 ms 16596 KB ok, correct split
12 Correct 1 ms 3676 KB ok, correct split
13 Correct 1 ms 3676 KB ok, correct split
14 Incorrect 1 ms 3676 KB invalid split: #1=0, #2=1, #3=4
15 Halted 0 ms 0 KB -