oj.uz

Submission #147654

# Submission time Handle Problem Language Result Execution time Memory
147654 2019-08-30T11:13:43 Z nandonathaniel Split the Attractions (IOI19_split) C++14
22 / 100
 899 ms 1048580 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;
vector<pii> V;
int warna[MAXN],subtree[MAXN],root1,root2,N,brp;
vector<int> adj[MAXN];
bool ada=false;

void dfs(int now,int par){
	subtree[now]=1;
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		dfs(nxt,now);
		subtree[now]+=subtree[nxt];
	}
}

void dfs2(int now,int par){
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		int kecil=min(subtree[nxt],N-subtree[nxt]),besar=N-kecil;
		if(kecil>=V[0].first && besar>=V[1].first){
			ada=true;
			if(kecil==subtree[nxt]){
				root1=nxt;
				root2=now;
			}
			else{
				root1=now;
				root2=nxt;
			}
			return;
		}
		dfs2(nxt,now);
	}
}

void dfs3(int now,int par,int id){
	if(brp==V[id].first)return;
	warna[now]=V[id].second;
	brp++;
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		dfs3(nxt,now,id);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	V.push_back({a,1});V.push_back({b,2});V.push_back({c,3});
	sort(V.begin(),V.end());
	memset(warna,0,sizeof(warna));
	vector<int> res;
	for(int i=0;i<n;i++)res.push_back(0);
	for(int i=0;i<p.size();i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	dfs(0,-1);
	dfs2(0,-1);
	if(!ada)return res;
	brp=0;
	dfs3(root1,root2,0);
	brp=0;
	dfs3(root2,root1,1);
	res.clear();
	for(int i=0;i<n;i++){
		if(warna[i]==0)warna[i]=V[2].second;
		res.push_back(warna[i]);
	}
	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:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++){
              ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 888 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 884 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Correct 83 ms 9840 KB ok, correct split
3 Correct 33 ms 5740 KB ok, correct split
4 Correct 5 ms 3064 KB ok, correct split
5 Correct 103 ms 11760 KB ok, correct split
6 Correct 96 ms 11704 KB ok, correct split
7 Correct 96 ms 11376 KB ok, correct split
8 Correct 119 ms 12628 KB ok, correct split
9 Correct 94 ms 11364 KB ok, correct split
10 Correct 28 ms 5264 KB ok, no valid answer
11 Correct 45 ms 6388 KB ok, no valid answer
12 Correct 71 ms 10052 KB ok, no valid answer
13 Correct 80 ms 9944 KB ok, no valid answer
14 Correct 64 ms 10352 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 899 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB ok, correct split
2 Runtime error 888 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -