#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<split.h>
using namespace std;
vector<int> ed[100001];
int need[3];
int n, m;
bool vis[100001];
int cld[100001];
int dfs(int ind)
{
int D=1;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D+=dfs(ed[ind][i]);
return (cld[ind] = D);
}
int bus(int ind)
{
bool z=true;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]] && cld[ed[ind][i]]>=n/2)
z=false;
if(n-cld[ind]>=n/2)
z=false;
if(z) return ind;
int D=-1;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D=max(bus(ed[ind][i]), D);
return D;
}
int centroide()
{
dfs(1);
memset(vis, false, sizeof(vis));
return bus(1);
}
vector<int> ans[3];
int rey;
typedef struct
{
int to, cld;
}Wasd;
bool operator < (const Wasd &a, const Wasd &b)
{
return a.cld < b.cld;
}
void expand(int ind)
{
vis[ind]=true;
ans[rey].push_back(ind);
if(ans[rey].size()==need[rey])
return;
vector<Wasd> ed2;
Wasd te;
for(int i = 0; i < ed[ind].size(); i++)
{
te.to=ed[ind][i];
te.cld=cld[te.to]-cld[ind];
if(te.cld<0) te.cld=cld[te.to];
ed2.push_back(te);
}
sort(ed2.begin(), ed2.end());
for(int i = 0; i < ed2.size(); i++)
if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
expand(ed2[i].to);
return;
}
int res[100001];
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
n=N; need[0]=a; need[1]=b; need[2]=c;
m=p.size();
int x, y;
for(int i = 0; i < m; i++)
{
x=p[i]; y=q[i];
ed[x].push_back(y);
ed[y].push_back(x);
}
int cnt = centroide();
if(need[0]<=max(need[1], need[2]) && need[0]>=min(need[2], need[1]))
rey=0;
else if(need[1]<=max(need[0], need[2]) && need[1]>=min(need[2], need[0]))
rey=1;
else rey=2;
memset(vis, false, sizeof(vis));
expand(cnt);
if(need[0]<=need[1] && need[0]<=need[2])
rey=0;
else if(need[1]<=need[0] && need[1]<=need[2])
rey=1;
else rey=2;
for(int i = 0; i < n; i++)
if(!vis[i])
{
expand(i);
if(ans[rey].size()==need[rey])
break;
ans[rey].clear();
}
for(int k = 0; k < 3; k++)
for(int i = 0; i < ans[k].size(); i++)
res[ans[k][i]]=k+1;
if(ans[0].size()>0 && ans[1].size()>0)
rey=2;
else if(ans[1].size()>0 && ans[2].size()>0)
rey=0;
else rey=1;
for(int i = 0; i < n; i++)
if(res[i]==0)
res[i] = rey+1;
vector<int> respuesta;
for(int i = 0; i < n; i++)
respuesta.push_back(res[i]);
return respuesta;
}
Compilation message
split.cpp: In function 'int dfs(int)':
split.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ed[ind].size(); i++)
~~^~~~~~~~~~~~~~~~
split.cpp: In function 'int bus(int)':
split.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ed[ind].size(); i++)
~~^~~~~~~~~~~~~~~~
split.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ed[ind].size(); i++)
~~^~~~~~~~~~~~~~~~
split.cpp: In function 'void expand(int)':
split.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans[rey].size()==need[rey])
~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ed[ind].size(); i++)
~~^~~~~~~~~~~~~~~~
split.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ed2.size(); i++)
~~^~~~~~~~~~~~
split.cpp:70:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
~~~~~~~~~~~~~~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans[rey].size()==need[rey])
~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ans[k].size(); i++)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2936 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2808 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
5548 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2808 KB |
ok, correct split |
| 2 |
Incorrect |
7 ms |
2808 KB |
invalid split: #1=0, #2=6, #3=0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2936 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
