oj.uz

Submission #772844

# Submission time Handle Problem Language Result Execution time Memory
772844 2023-07-04T11:48:24 Z Abrar_Al_Samit Split the Attractions (IOI19_split) C++17
22 / 100
 434 ms 1048576 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int nax = 1e5 + 3;

//subtask 1&3

vector<int>g[nax];
int m, n;
int sub[nax];
bool taken[nax];


int dfs(int v, int p) {
	sub[v] = 1;
	for(int u : g[v]) if(u!=p) {
		sub[v] += dfs(u, v);
	}
	return sub[v];
}
int get_centroid(int v, int p) {
	for(int u : g[v]) if(u!=p) {
		if(sub[u]*2>n) {
			return get_centroid(u, v);
		}
	}
	return v;
}
vector<int> find_split(int N, int A, int B, int C, 
	vector<int> p, vector<int> q) {
	n = N;

	vector<int>sz = {A, B, C}, ord = {0, 1, 2};	
	sort(ord.begin(), ord.end(), [&] (int i, int j) {
		return sz[i] < sz[j];
	});

	m = p.size();
	for(int i=0; i<m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}

	dfs(0, 0);

	int ct = get_centroid(0, 0);

	dfs(ct, ct);

	int bc = -1;
	for(int u : g[ct]) {
		if(sub[u]>=sz[ord[0]]) {
			bc = u;
			break;
		}
	}
	if(bc==-1) {
		return vector<int>(n, 0);
	}

	taken[ct] = 1;

	vector<int>g1;
	queue<int>qu;
	qu.push(bc);

	while(g1.size()<sz[ord[0]]) {
		int v = qu.front();
		qu.pop();

		if(taken[v]) continue;
		taken[v] = 1;
		g1.push_back(v);

		for(int u : g[v]) if(!taken[u]) {
			qu.push(u);
		}
	}

	taken[ct] = 0;
	while(!qu.empty()) qu.pop();
	qu.push(ct);
	vector<int>g2;
	while(g2.size()<sz[ord[1]]) {
		int v = qu.front();
		qu.pop();

		if(taken[v]) continue;
		taken[v] = 1;
		g2.push_back(v);

		for(int u : g[v]) if(!taken[u]) {
			qu.push(u);
		}
	}

	vector<int>res(n, 0);
	for(int x : g1) {
		res[x] = ord[0]+1;
	}
	for(int x : g2) {
		res[x] = ord[1]+1;
	}
	for(int i=0; i<n; ++i) if(res[i]==0) {
		res[i] = ord[2]+1;
	}
	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:68:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   68 |  while(g1.size()<sz[ord[0]]) {
split.cpp:85:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   85 |  while(g2.size()<sz[ord[1]]) {

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB ok, correct split
2 Runtime error 434 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 2644 KB ok, correct split
2 Runtime error 397 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 2 ms 2644 KB ok, correct split
2 Correct 45 ms 9968 KB ok, correct split
3 Correct 16 ms 5404 KB ok, correct split
4 Correct 2 ms 2644 KB ok, correct split
5 Correct 47 ms 11768 KB ok, correct split
6 Correct 60 ms 11548 KB ok, correct split
7 Correct 45 ms 11612 KB ok, correct split
8 Correct 48 ms 12472 KB ok, correct split
9 Correct 48 ms 11572 KB ok, correct split
10 Correct 14 ms 4820 KB ok, no valid answer
11 Correct 20 ms 5992 KB ok, no valid answer
12 Correct 37 ms 9552 KB ok, no valid answer
13 Correct 39 ms 9320 KB ok, no valid answer
14 Correct 42 ms 9668 KB ok, no valid answer

Subtask #4
0 / 24.0

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