This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
int extremo1,extremo2,numvis;
vector<int>vis,siguiente[100005];
queue<int>cola;
int encuentraextremo(int origen,int color)
{
int distancia[100005],ultimo;
numvis=color;
cola.push(origen);
distancia[origen]=0;
vis[origen]=numvis;
while(!cola.empty())
{
int actual=cola.front();
cola.pop();
for(int i=0;i<siguiente[actual].size();i++)
{
int nuevo=siguiente[actual][i];
if(vis[nuevo]!=numvis)
{
vis[nuevo]=numvis;
distancia[nuevo]=distancia[actual]+1;
cola.push(nuevo);
}
}
ultimo=actual;
}
return ultimo;
}
int visita(int telementos,int origen,int grupo)
{
int tvisitados=0;
numvis=grupo;
cola.push(origen);
while((!cola.empty()) and tvisitados<telementos)
{
int actual=cola.front();
cola.pop();
if(vis[actual]>3)
{
vis[actual]=numvis;
tvisitados++;
for(int i=0;i<siguiente[actual].size();i++)
{
int nuevo=siguiente[actual][i];
if(vis[nuevo]!=numvis)
cola.push(nuevo);
}
}
}
while(!cola.empty())
cola.pop();
return tvisitados;
}
void rellena(int grupo,int tnumeros)
{
for(int i=0;i<tnumeros;i++)
{
if(vis[i]>3)
vis[i]=grupo;
}
}
vector<int> find_split(int tnodos,int telementos1,int telementos2,int telementos3,vector<int> origen,vector<int> destino)
{
for(int i=0;i<origen.size();i++)
{
siguiente[origen[i]].push_back(destino[i]);
siguiente[destino[i]].push_back(origen[i]);
}
vis.resize(tnodos);
extremo1=encuentraextremo(0,5);
extremo2=encuentraextremo(extremo1,4);
if(telementos1<=telementos3 and telementos2<=telementos3)
{
visita(telementos1,extremo1,1);
if(telementos2==visita(telementos2,extremo2,2))
{
rellena(3,tnodos);
}
else
{
vis.resize(0);
vis.resize(tnodos);
}
}
else
{
if(telementos1<=telementos2 and telementos3<=telementos2)
{
visita(telementos1,extremo1,1);
if(telementos3==visita(telementos3,extremo2,3))
{
rellena(2,tnodos);
}
else
{
vis.resize(0);
vis.resize(tnodos);
}
}
else
{
visita(telementos2,extremo1,2);
if(telementos3==visita(telementos3,extremo2,3))
{
rellena(1,tnodos);
}
else
{
vis.resize(0);
vis.resize(tnodos);
}
}
}
return vis;
}
Compilation message (stderr)
split.cpp: In function 'int encuentraextremo(int, int)':
split.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<siguiente[actual].size();i++)
~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int visita(int, int, int)':
split.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<siguiente[actual].size();i++)
~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<origen.size();i++)
~^~~~~~~~~~~~~~
split.cpp: In function 'int encuentraextremo(int, int)':
split.cpp:30:12: warning: 'ultimo' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ultimo;
^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |