Submission #427643

#	Time	Username	Problem	Language	Result	Execution time	Memory
427643		APROHACK	Split the Attractions (IOI19_split)	C++14	7 / 100	132 ms	13384 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define PB push_back
#define distancia first
#define hacia second
using namespace std;
vector<int>ady[100001];
vector<int>stt, stt2;
int A, B, N, dist[100001], tama, tamb, tamc, cnt;
bool reco[100001], reco2[100001];
int bfs1(int start){//hallar nodo A
	
	int rta=0;
	queue<pair<int, int> >quiu;
	bool recorrido[100001];
	quiu.push({0, start});
	//memset(recorrido, false, sizeof recorrido);
	for(int i = 0 ; i < N ; i++)recorrido[i]=false;
	recorrido[start]=true;
	while(quiu.size()){
		int u = quiu.front().hacia, di=quiu.front().distancia;
		for(auto i : ady[u]){
			if(recorrido[i])continue;
			quiu.push({di+1, i});
			recorrido[i]=true;
			rta=i;
		}
		quiu.pop();
	}return rta;
}
int bfs2(int start){// hallar nodo B con respecto a A
	int rta=0;
	queue<pair<int, int> >quiu;
	bool recorrido[100001];
	//memset(recorrido, false, sizeof recorrido);
	quiu.push({0, start});
	dist[start]=0;
	long long cont = 0;
	for(int i = 0 ; i < N ; i++)recorrido[i]=false;
	recorrido[start]=true;
	while(quiu.size()){
		int u = quiu.front().hacia, di=quiu.front().distancia;
		//cout<<u<<endl;
		if(cont==tamb){
			return 1;
		}else{
			stt2.PB(u);
			reco[u]=true;
			reco2[u]=true;
			cont++;
			for(auto i : ady[u]){
				if(recorrido[i])continue;
				quiu.push({0, i});
				dist[i]=0;
				recorrido[i]=true;
				//rta=i;
			}
		}
		quiu.pop();
	}return rta;
}
bool dfs(int node){
	
	for(auto i:ady[node]){
		if(reco2[i]||reco[i])continue;
		cnt++;
		reco2[i]=true;
		dfs(i);
	}
	if(cnt>=tama){
		if(stt.size()<tama){
			reco[node]=true;
			stt.PB(node);
		}
		return true;
	}else return false;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res;
	N=n;
	for(int i = 0 ; i < p.size () ; i++){
		ady[p[i]].PB(q[i]);
		ady[q[i]].PB(p[i]);
	}
	tama=a, tamb=b, tamc=c;
	if(tama>tamc)swap(tama, tamc);
	if(tamb>tamc)swap(tamb, tamc);
	if(tama>tamb)swap(tama, tamb);
	A=bfs1(1);//hallar nodo A
	//cout<<A<<endl;
	B=bfs2(A); // hallar nodo B con respecto a A
	//cout<<B<<endl;
	bool sepudo=false;
	for(int i = 0 ; i < n ; i++){
		if(!reco2[i]){
			cnt=0;
			if(dfs(i)){
				sepudo=true;
				break;
			}
		}
	}
	//bfs3(B); // hallar conjunto desde B con distancias de A
	//for(int i = 0 ; i < n ; i++)cout<<dist[i]<<" ";
	//res.resize(n);
	if(sepudo) {
		int temp=(n-stt.size());
		temp-=stt2.size();
		if(temp==c)temp=3;
		else if(temp==b)temp=2;
		else temp=1;
		for(int i = 0 ; i < n ; i++){
			res.PB(temp);
		}
		int temp2;
		temp2=stt.size();
		if(temp2==c&&temp!=3)temp2=3;
		else if(temp2==b&&temp!=2)temp2=2;
		else temp2=1;
		//temp=1;
		for(auto i:stt){
			res[i]=temp2;
		}
		int temp3=stt2.size();
		if(temp3==c&&temp!=3&&temp2!=3)temp3=3;
		else if(temp3==b&&temp!=2&&temp2!=2)temp3=2;
		else temp3=1;
		for(auto i:stt2){
			res[i]=temp3;
		}
		
	} else {
		for(int i = 0 ; i < n ; i++){
			res.PB(0);
		}
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'int bfs2(int)':
split.cpp:42:31: warning: unused variable 'di' [-Wunused-variable]
   42 |   int u = quiu.front().hacia, di=quiu.front().distancia;
      |                               ^~
split.cpp: In function 'bool dfs(int)':
split.cpp:71:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   if(stt.size()<tama){
      |      ~~~~~~~~~~^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0 ; i < p.size () ; i++){
      |                  ~~^~~~~~~~~~~

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