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 <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
vector<int> res;
vector<int> v[nmax];
pair<int,int> C[3];
int viz[nmax],q[nmax],w[nmax],tt[nmax];
int i,n;
void sterge(int A,int B)
{
for(int it=0;it<2;it++)
{
for(int i=0;i<v[A].size();i++)
if(v[A][i]==B)
{
swap(v[A][i],v[A].back());
v[A].pop_back();
}
}
}
void et(int x,int cate,int col)
{
int p,u;
for(i=0;i<n;i++)
viz[i]=0;
viz[x]=1;
q[u=1]=x;
for(p=1;p<=u;p++)
{
x=q[p];
for(int i=0;i<v[x].size();i++)
if(!viz[v[x][i]])
{
q[++u]=v[x][i];
viz[v[x][i]]=1;
}
}
for(i=1;i<=cate;i++)
res[q[i]]=col;
}
bool gasit;
void solve(int x)
{
w[x]=1;
for(int i=0;i<v[x].size();i++)
if((!w[v[x][i]]))
{
tt[v[x][i]]=x;
solve(v[x][i]);
w[x]+=w[v[x][i]];
}
if(!gasit)
{
if(w[x]>=C[0].first&&n-w[x]>=C[1].first)
{
sterge(x,tt[x]);
et(x,C[0].first,C[0].second);
et(tt[x],C[1].first,C[1].second);
gasit=1;
}
else
{
if(w[x]>=C[1].first&&n-w[x]>=C[0].first)
{
sterge(x,tt[x]);
et(x,C[1].first,C[1].second);
et(tt[x],C[0].first,C[0].second);
gasit=1;
}
}
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
n=nn;
for(i=0;i<p.size();i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
res.resize(n);
for(i=0;i<n;i++)
res[i]=0;
pair<int,int> v[3];
C[0]={a,1};
C[1]={b,2};
C[2]={c,3};
sort(C,C+3);
solve(0);
if(gasit)
{
int oth=(C[0].second^C[1].second);
for(i=0; i<n; i++)
if(!res[i])
res[i]=oth;
}
return res;
}
Compilation message (stderr)
split.cpp: In function 'void sterge(int, int)':
split.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[A].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'void et(int, int, int)':
split.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'void solve(int)':
split.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:77:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<p.size();i++)
~^~~~~~~~~
split.cpp:85:19: warning: unused variable 'v' [-Wunused-variable]
pair<int,int> v[3];
^
# | 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... |