oj.uz

답안 #147653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147653 2019-08-30T11:13:03 Z nandonathaniel Split the Attractions (IOI19_split) C++14
0 / 100
 892 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);
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3064 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3064 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3064 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 892 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3064 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -