Submission #427095

#	Time	Username	Problem	Language	Result	Execution time	Memory
427095		APROHACK	Split the Attractions (IOI19_split)	C++14	18 / 100	142 ms	11412 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;
bool reco[100001];
int bfs1(int start){
	
	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){
	int rta=0;
	queue<pair<int, int> >quiu;
	bool recorrido[100001];
	//memset(recorrido, false, sizeof recorrido);
	quiu.push({0, start});
	dist[start]=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;
		for(auto i : ady[u]){
			if(recorrido[i])continue;
			quiu.push({di+1, i});
			dist[i]=di+1;
			recorrido[i]=true;
			rta=i;
		}
		quiu.pop();
	}return rta;
}
int bfs3(int start){
	int rta=0, cont=0;
	priority_queue<pair<int, int> >quiu;
	bool recorrido[100001];
	//memset(recorrido, false, sizeof recorrido);
	quiu.push({dist[start], start});
	//dist[start]=0;
	for(int i = 0 ; i < N ; i++)recorrido[i]=false;
	recorrido[start]=true;
	while(quiu.size()){
		
		int u = quiu.top().hacia, di=quiu.top().distancia;
		//cout<<u<<endl;
		stt.PB(u);
		reco[u]=true;
		cont++;
		if(cont==tamb){
			return 1;
		}
		quiu.pop();
		for(auto i : ady[u]){
			if(recorrido[i])continue;
			quiu.push({dist[i], i});
			//dist[i]=di+1;
			recorrido[i]=true;
			rta=i;
		}
		
	}return rta;
}
int bfs4(int start){
	int rta=-1, cont=0;
	queue<pair<int, int> >quiu;
	bool recorrido[100001];
	//memset(recorrido, false, sizeof recorrido);
	quiu.push({dist[start], start});
	//dist[start]=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;
		stt2.PB(u);
		reco[u]=true;
		cont++;
		if(cont==tama){
			return 1;
		}
		quiu.pop();
		for(auto i : ady[u]){
			if(recorrido[i]||reco[i])continue;
			quiu.push({dist[i], i});
			//dist[i]=di+1;
			recorrido[i]=true;
			//rta=i;
		}
		
	}return rta;
}
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);
	//cout<<A<<endl;
	B=bfs2(A);
	//cout<<B<<endl;
	bfs3(B);
	//for(int i = 0 ; i < n ; i++)cout<<dist[i]<<" ";
	//res.resize(n);
	if(bfs4(A)!=-1) {
		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 bfs3(int)':
split.cpp:64:29: warning: unused variable 'di' [-Wunused-variable]
   64 |   int u = quiu.top().hacia, di=quiu.top().distancia;
      |                             ^~
split.cpp: In function 'int bfs4(int)':
split.cpp:93:31: warning: unused variable 'di' [-Wunused-variable]
   93 |   int u = quiu.front().hacia, di=quiu.front().distancia;
      |                               ^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i = 0 ; i < p.size () ; i++){
      |                  ~~^~~~~~~~~~~

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