Submission #986949

#	Time	Username	Problem	Language	Result	Execution time	Memory
986949		PagodePaiva	Split the Attractions (IOI19_split)	C++17	11 / 100	66 ms	16592 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

vector <int> g[N];
int pai[N];
int folha;
int mark[N];

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

int res[N];

void solve(int v, int &tam){
	if(tam == 0) return;
	tam--;
	res[v] = 2;
	mark[v] = 1;
	for(auto x : g[v]){
		if(mark[x]) continue;
		solve(x, tam);
	}
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = p.size();
	for(int i = 0;i < m;i++){
		int a = p[i], b = q[i];
		a++;
		b++;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	memset(mark, 0, sizeof mark);
	res[folha] = 1;
	mark[folha] = 1;
	solve(pai[folha], b);
	vector <int> ans;
	for(int i = 1;i <= n;i++){
		if(res[i] == 0) res[i] = 3;
		ans.push_back(res[i]);
	}
	return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36