#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
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 |
1 |
Correct |
7 ms |
2680 KB |
ok, correct split |
2 |
Correct |
7 ms |
2680 KB |
ok, correct split |
3 |
Correct |
7 ms |
2680 KB |
ok, correct split |
4 |
Correct |
6 ms |
2680 KB |
ok, correct split |
5 |
Correct |
7 ms |
2680 KB |
ok, correct split |
6 |
Correct |
7 ms |
2680 KB |
ok, correct split |
7 |
Correct |
118 ms |
8184 KB |
ok, correct split |
8 |
Correct |
127 ms |
8416 KB |
ok, correct split |
9 |
Correct |
127 ms |
8184 KB |
ok, correct split |
10 |
Correct |
112 ms |
8184 KB |
ok, correct split |
11 |
Correct |
125 ms |
8312 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2680 KB |
ok, correct split |
2 |
Correct |
6 ms |
2680 KB |
ok, correct split |
3 |
Correct |
7 ms |
2680 KB |
ok, correct split |
4 |
Correct |
129 ms |
9464 KB |
ok, correct split |
5 |
Correct |
105 ms |
8312 KB |
ok, correct split |
6 |
Correct |
106 ms |
8184 KB |
ok, correct split |
7 |
Correct |
122 ms |
8184 KB |
ok, correct split |
8 |
Correct |
155 ms |
10744 KB |
ok, correct split |
9 |
Correct |
123 ms |
8184 KB |
ok, correct split |
10 |
Correct |
65 ms |
8944 KB |
ok, correct split |
11 |
Correct |
69 ms |
8944 KB |
ok, correct split |
12 |
Correct |
67 ms |
8944 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2680 KB |
ok, correct split |
2 |
Incorrect |
102 ms |
8312 KB |
jury found a solution, contestant did not |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2808 KB |
ok, correct split |
2 |
Correct |
6 ms |
2680 KB |
ok, no valid answer |
3 |
Correct |
6 ms |
2680 KB |
ok, correct split |
4 |
Correct |
6 ms |
2680 KB |
ok, correct split |
5 |
Correct |
7 ms |
2680 KB |
ok, correct split |
6 |
Correct |
6 ms |
2680 KB |
ok, correct split |
7 |
Correct |
7 ms |
2680 KB |
ok, correct split |
8 |
Correct |
7 ms |
2680 KB |
ok, correct split |
9 |
Correct |
9 ms |
2808 KB |
ok, correct split |
10 |
Correct |
9 ms |
2936 KB |
ok, correct split |
11 |
Correct |
6 ms |
2680 KB |
ok, correct split |
12 |
Incorrect |
9 ms |
2936 KB |
jury found a solution, contestant did not |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2680 KB |
ok, correct split |
2 |
Correct |
7 ms |
2680 KB |
ok, correct split |
3 |
Correct |
7 ms |
2680 KB |
ok, correct split |
4 |
Correct |
6 ms |
2680 KB |
ok, correct split |
5 |
Correct |
7 ms |
2680 KB |
ok, correct split |
6 |
Correct |
7 ms |
2680 KB |
ok, correct split |
7 |
Correct |
118 ms |
8184 KB |
ok, correct split |
8 |
Correct |
127 ms |
8416 KB |
ok, correct split |
9 |
Correct |
127 ms |
8184 KB |
ok, correct split |
10 |
Correct |
112 ms |
8184 KB |
ok, correct split |
11 |
Correct |
125 ms |
8312 KB |
ok, correct split |
12 |
Correct |
7 ms |
2680 KB |
ok, correct split |
13 |
Correct |
6 ms |
2680 KB |
ok, correct split |
14 |
Correct |
7 ms |
2680 KB |
ok, correct split |
15 |
Correct |
129 ms |
9464 KB |
ok, correct split |
16 |
Correct |
105 ms |
8312 KB |
ok, correct split |
17 |
Correct |
106 ms |
8184 KB |
ok, correct split |
18 |
Correct |
122 ms |
8184 KB |
ok, correct split |
19 |
Correct |
155 ms |
10744 KB |
ok, correct split |
20 |
Correct |
123 ms |
8184 KB |
ok, correct split |
21 |
Correct |
65 ms |
8944 KB |
ok, correct split |
22 |
Correct |
69 ms |
8944 KB |
ok, correct split |
23 |
Correct |
67 ms |
8944 KB |
ok, correct split |
24 |
Correct |
7 ms |
2680 KB |
ok, correct split |
25 |
Incorrect |
102 ms |
8312 KB |
jury found a solution, contestant did not |
26 |
Halted |
0 ms |
0 KB |
- |