#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#include <split.h>
#define mp make_pair
#define pb push_back
/*#define a first
#define b second*/
vector<int> adj[200001];
vector<int> stac;
int bb;
int aa;
int cc;
int ind7;
int ind2=0;
int co=0;
int vis[200001];
int dd;
vector<int> anss;
void dfs(int no){
stac.pb(no);
if(stac.size()==bb){
return ;
}
for(int j=0;j<adj[no].size();j++){
if(stac.size()==bb){
return;
}
int nn=adj[no][j];
if(vis[nn]==0){
vis[nn]=1;
dfs(nn);
}
}
}
void dfs2(int no){
co+=1;
if(co<=aa){
anss[no]=1;
}
else if(co<=aa+bb){
anss[no]=2;
}
else{
anss[no]=3;
}
for(int j=0;j<adj[no].size();j++){
int nn=adj[no][j];
if(vis[nn]==0){
vis[nn]=1;
dfs2(nn);
}
}
}
int size2[200001];
vector<pair<int,int>> pos;
void dfs3(int no,int par=-1){
size2[no]=1;
int st=1;
for(int j=0;j<adj[no].size();j++){
int nn=adj[no][j];
if(nn==par){
continue;
}
dfs3(nn,no);
size2[no]+=size2[nn];
if(size2[nn]>=aa){
st=0;
}
}
if(st==1 and size2[no]>=aa){
pos.pb(mp(no,par));
}
}
void dfs4(int no,int par){
co+=1;
anss[no]=1;
if(co==aa){
return;
}
for(int j=0;j<adj[no].size();j++){
if(co==aa){
return;
}
int nn=adj[no][j];
if(nn==par){
continue;
}
if(ind7==nn){
continue;
}
dfs4(nn,no);
}
}
void dfs5(int no,int par){
co+=1;
anss[no]=0;
if(co==bb){
return;
}
for(int j=0;j<adj[no].size();j++){
if(co==aa){
return;
}
int nn=adj[no][j];
if(nn==par){
continue;
}
if(ind7==nn){
continue;
}
dfs5(nn,no);
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
int m=p.size();
vector<int> ss;
ss.pb(a);
ss.pb(b);
ss.pb(c);
sort(ss.begin(),ss.end());
a=ss[0];
b=ss[1];
c=ss[1];
bb=b;
aa=a;
cc=c;
memset(vis,0,sizeof(vis));
for(int i=0;i<m;i++){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
if(a==1){
//st2
vis[0]=1;
dfs(0);
int st=1;
vector<int> ans;
for(int i=0;i<n;i++){
ans.pb(0);
}
for(int j=0;j<b;j++){
ans[stac[j]]=(int)2;
}
for(int i=0;i<n;i++){
if(ans[i]==2){
continue;
}
ans[i]=st;
st=3;
}
return ans;
}
int st=0;
int ind=-1;
for(int i=0;i<n;i++){
anss.pb(0);
}
for(int i=0;i<n;i++){
if(adj[i].size()>2){
st=1;
}
else if(adj[i].size()==1){
ind=i;
}
}
if(st==1){
vector<int> aa;
if(m==n-1){
dfs3(0,-1);
ind7=-1;
int par5=-1;
/* for(int i=0;i<n;i++){
cout<<size[i]<<" ";
}
cout<<endl;*/
for(int j=0;j<pos.size();j++){
if(n-size2[pos[j].first]>=a){
ind7=pos[j].first;
par5=pos[j].second;
break;
}
}
if(ind7==-1){
return anss;
}
if(size2[ind7]<b){
int ind8=ind7;
ind7=0;
dfs4(ind8,par5);
ind7=ind8;
dfs5(0,-1);
for(int i=0;i<n;i++){
if(anss[i]==0){
anss[i]=3;
}
}
}
else{
int ind8=ind7;
ind7=0;
dfs5(ind8,par5);
ind7=ind8;
dfs4(0,-1);
for(int i=0;i<n;i++){
if(anss[i]==0){
anss[i]=3;
}
}
}
return anss;
}
return aa;
}
else{
//st1
if(ind==-1){
ind=0;
}
vis[ind]=1;
dfs2(ind);
}
return anss;
}
/*int main(){
vector<int> ans10;
ans10=find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
for(int i=0;i<ans10.size();i++){
cout<<ans10[i]<<endl;
}
return 0;
}*/
Compilation message
split.cpp: In function 'void dfs(int)':
split.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(stac.size()==bb){
~~~~~~~~~~~^~~~
split.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
split.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(stac.size()==bb){
~~~~~~~~~~~^~~~
split.cpp: In function 'void dfs2(int)':
split.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int)':
split.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int, int)':
split.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs5(int, int)':
split.cpp:106:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:184:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<pos.size();j++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5756 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
5752 KB |
ok, correct split |
| 3 |
Correct |
8 ms |
5752 KB |
ok, correct split |
| 4 |
Incorrect |
8 ms |
5752 KB |
invalid split: #1=1, #2=1, #3=2 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5752 KB |
ok, correct split |
| 2 |
Correct |
9 ms |
5752 KB |
ok, correct split |
| 3 |
Correct |
8 ms |
5880 KB |
ok, correct split |
| 4 |
Correct |
100 ms |
12260 KB |
ok, correct split |
| 5 |
Correct |
79 ms |
11380 KB |
ok, correct split |
| 6 |
Correct |
82 ms |
11164 KB |
ok, correct split |
| 7 |
Incorrect |
88 ms |
12912 KB |
invalid split: #1=1, #2=49999, #3=50000 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5752 KB |
invalid split: #1=1, #2=2, #3=2 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5624 KB |
WA in grader: Invalid length of the result. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5756 KB |
ok, correct split |
| 2 |
Correct |
8 ms |
5752 KB |
ok, correct split |
| 3 |
Correct |
8 ms |
5752 KB |
ok, correct split |
| 4 |
Incorrect |
8 ms |
5752 KB |
invalid split: #1=1, #2=1, #3=2 |
| 5 |
Halted |
0 ms |
0 KB |
- |
