oj.uz

Submission #986881

# Submission time Handle Problem Language Result Execution time Memory
986881 2024-05-21T13:46:53 Z PagodePaiva Split the Attractions (IOI19_split) C++17
0 / 100
 602 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 < p.size();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];
      |      ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 1;i < p.size();i++){
      |                ~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3676 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 Runtime error 602 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 Incorrect 1 ms 3676 KB invalid split: #1=0, #2=1, #3=2
2 Halted 0 ms 0 KB -