Submission #422724

#	Time	Username	Problem	Language	Result	Execution time	Memory
422724		MeGustaElArroz23	Split the Attractions (IOI19_split)	C++14	18 / 100	125 ms	15984 KiB

split

#include "split.h"
#include <cstdio>
#include <cassert>

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<bool,bool> pbb;
typedef vector<pbb> vbb;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const ll INF=1000000001;

vi solve1(int n, int a, int b, int c, vvi conexiones){
	vi res(n,0);
	queue<int> cola;
	cola.push(0);
	vb porvisitar(n,true);
	while (cola.size()){
		int x=cola.front();
		cola.pop();
		if (porvisitar[x]){
			porvisitar[x]=false;
			if (b){
				res[x]=2;
				b--;
			}
			else if (c){
				res[x]=3;
				c--;
			}
			else res[x]=1;

			for (int y:conexiones[x]) cola.push(y);
		}
	}
	return res;
}

vi solve2(int n, int a, int b, int c, vvi conexiones){
	int inicio=0;
	for (int i=0;i<n;i++){
		if (conexiones[i].size()==0) inicio=i;
	}
	vi res(n,0);
	stack<int> cola;
	cola.push(inicio);
	vb porvisitar(n,true);
	while (cola.size()){
		int x=cola.top();
		cola.pop();
		if (porvisitar[x]){
			porvisitar[x]=false;
			if (b){
				res[x]=2;
				b--;
			}
			else if (c){
				res[x]=3;
				c--;
			}
			else res[x]=1;

			for (int y:conexiones[x]) cola.push(y);
		}
	}
	return res;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res;
	vvi conexiones(n);
	int m=p.size();
	for (int i=0;i<m;i++){
		conexiones[p[i]].push_back(q[i]);
		conexiones[q[i]].push_back(p[i]);
	}
	if (a==1) return solve1(n,a,b,c,conexiones);
	else return  solve2(n,a,b,c,conexiones);
}

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