oj.uz

Submission #986882

# Submission time Handle Problem Language Result Execution time Memory
986882 2024-05-21T13:47:35 Z PagodePaiva Split the Attractions (IOI19_split) C++17
22 / 100
 565 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 Correct 2 ms 3672 KB ok, correct split
2 Runtime error 565 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB ok, correct split
2 Runtime error 548 ms 1048576 KB Execution killed with signal 9
3 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 40 ms 9948 KB ok, correct split
3 Correct 20 ms 6620 KB ok, correct split
4 Correct 1 ms 3676 KB ok, correct split
5 Correct 43 ms 12508 KB ok, correct split
6 Correct 43 ms 12248 KB ok, correct split
7 Correct 43 ms 11992 KB ok, correct split
8 Correct 47 ms 13440 KB ok, correct split
9 Correct 42 ms 11996 KB ok, correct split
10 Correct 13 ms 5976 KB ok, no valid answer
11 Correct 19 ms 7004 KB ok, no valid answer
12 Correct 35 ms 10192 KB ok, no valid answer
13 Correct 37 ms 9948 KB ok, no valid answer
14 Correct 33 ms 10180 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 558 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 2 ms 3672 KB ok, correct split
2 Runtime error 565 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -