oj.uz

Submission #987506

# Submission time Handle Problem Language Result Execution time Memory
987506 2024-05-22T22:15:06 Z PagodePaiva Split the Attractions (IOI19_split) C++17
0 / 100
 24 ms 7260 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2510;

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

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

vector <int> aux[N];

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

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	for(int i = 0;i < p.size();i++){
		int x = p[i]+1, y = q[i]+1;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	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 st = 1;st <= n;st++){
		memset(mark, 0, sizeof mark);
		dfs(st, st);
		for(auto v : g[st]){
			if(sz[v] >= a and n-sz[v] >= b){
				solve(v, a, b);
				vector <int> ans;
				for(int i = 1;i <= n;i++) ans.push_back(res[i]);
				return ans;
			}
		}
	}
	vector <int> ans;
	for(int i = 0;i < n;i++) ans.push_back(0);
	return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0;i < p.size();i++){
      |                ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 344 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 ms 560 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Incorrect 1 ms 348 KB jury found a solution, contestant did not
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Runtime error 24 ms 7260 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Runtime error 16 ms 4956 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 348 KB ok, no valid answer
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 504 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 1 ms 348 KB ok, correct split
8 Correct 1 ms 348 KB ok, correct split
9 Correct 2 ms 860 KB ok, correct split
10 Correct 2 ms 824 KB ok, correct split
11 Correct 1 ms 604 KB ok, correct split
12 Correct 2 ms 860 KB ok, correct split
13 Correct 1 ms 348 KB ok, correct split
14 Correct 1 ms 600 KB ok, correct split
15 Correct 1 ms 344 KB ok, correct split
16 Correct 1 ms 348 KB ok, correct split
17 Incorrect 1 ms 348 KB jury found a solution, contestant did not
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 344 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 ms 560 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Incorrect 1 ms 348 KB jury found a solution, contestant did not
7 Halted 0 ms 0 KB -