oj.uz

Submission #987214

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

vector <int> g[N];
vector <int> tipos = {1, 2, 3};
int pai[N];
int sz[N];
int mark[N];
int n;
void dfs(int v, int p){
	mark[v] = 1;
	sz[v] = 1;
	pai[v] = p;
	for(auto x : g[v]){
		if(mark[x]) continue;
		dfs(x, v);
		sz[v] += sz[x];
	}
	return;
}

vector <int> ar[N];
int res[N];

void dfs2(int v, int p, int &tam, int typ){
	if(tam == 0) return;
	res[v] = typ;
	tam--;
	for(auto x : ar[v]){
		if(x == p) continue;
		dfs2(x,v,tam,typ);
	}
	return;
}

void solve(int v, int a, int b){
	for(int i = 1;i <= n;i++){
		if(pai[i] == i) continue;
		ar[i].push_back(pai[i]);
		ar[pai[i]].push_back(i);
	}
	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;
	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(int i = 1;i <= n;i++){
			if(sz[i] >= b and n-sz[i] >= a){
				swap(a, b);
				swap(tipos[0], tipos[1]);
			}
			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;
			}
		}
	}
	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 344 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Runtime error 15 ms 3912 KB Execution killed with signal 11
8 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 0 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Runtime error 29 ms 5460 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 15 ms 3916 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 348 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 4 ms 1016 KB ok, correct split
10 Correct 2 ms 860 KB ok, correct split
11 Correct 1 ms 604 KB ok, correct split
12 Correct 2 ms 856 KB ok, correct split
13 Correct 1 ms 348 KB ok, correct split
14 Correct 1 ms 348 KB ok, correct split
15 Correct 1 ms 348 KB ok, correct split
16 Correct 1 ms 348 KB ok, correct split
17 Correct 1 ms 348 KB ok, correct split
18 Correct 1 ms 348 KB ok, correct split
19 Correct 1 ms 604 KB ok, correct split
20 Correct 1 ms 604 KB ok, correct split
21 Correct 2 ms 860 KB ok, correct split
22 Correct 2 ms 860 KB ok, correct split
23 Correct 2 ms 860 KB ok, correct split
24 Correct 2 ms 860 KB ok, correct split
25 Correct 2 ms 856 KB ok, correct split
26 Incorrect 54 ms 820 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Runtime error 15 ms 3912 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -