#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector< vector<int> > v(200001);
vector< pair<vector<int>,int> >g(200001);
bool cmp(pair<vector<int>,int> i,pair<vector<int>,int> j)
{
return i.first.size()<j.first.size();
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<int> rez(n);
for(int i=0;i<n;i++)
{
rez[i]=0;
}
for(int i=0;i<p.size();i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
if(a==1)
{
if(b>c)swap(b,c);
for(int i=0;i<n;i++)
{
g[i]=make_pair(v[i],i);
}
bool vis[n];
queue<int> q;
for(int i=0;i<n;i++)
{
rez[i]=0;
vis[i]=0;
}
sort(g.begin(),g.begin()+n,cmp);
int start=g[0].second;
vis[start]=1;
rez[start]=1;
int br=0;
int node=g[n-1].second;
q.push(node);
vis[node]=1;
while(!q.empty())
{
int cur=q.front();
q.pop();
rez[cur]=2;
br++;
if(br==b-1)break;
for(int i=0;i<v[node].size();i++)
{
if(!vis[v[node][i]])
{
vis[v[node][i]]=1;
q.push(v[node][i]);
}
}
}
for(int i=0;i<n;i++)
{
if(rez[i]==0)rez[i]=3;
}
}
else
{
int ind=-1;
for(int i=0;i<n;i++)
{
if(v[i].size()==1)
{
ind=i;
break;
}
}
int br=1;
rez[ind]=1;
int prev=ind;
int cur=v[ind][0];
while(br<a+b)
{
if(br<a)
{
rez[cur]=1;
}
else
{
rez[cur]=2;
}
br++;
if(v[cur].size()==1)
{
prev=cur;
cur=v[cur][0];
}
else
{
if(v[cur][0]==prev)
{
prev=cur;
cur=v[cur][1];
}
else
{
prev=cur;
cur=v[cur][0];
}
}
}
for(int i=0;i<n;i++)
{
if(rez[i]==0)rez[i]=3;
}
}
return rez;
}
/*int main()
{
int n,m,a,b,c;
cin >> n >>m >>a >> b >> c;
vector<int> p(m);
vector<int> q(m);
for(int i=0;i<m;i++)
{
cin >> p[i]>> q[i];
}
vector<int> t=find_split(n,a,b,c,p,q);
for(int i=0;i<n;i++)
{
cout << t[i]<<' ';
}
}
*/
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++)
~^~~~~~~~~
split.cpp:51:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[node].size();i++)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11256 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11256 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11256 KB |
ok, correct split |
| 2 |
Incorrect |
78 ms |
16504 KB |
invalid split: #1=1, #2=4, #3=99995 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
11260 KB |
invalid split: #1=3, #2=2, #3=4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
11256 KB |
invalid split: #1=1, #2=2, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
