#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
bitset<100100>messg;
void gooo(int nod){
messg[nod]=Move(nod-1);
}
vector<int>path;
namespace ioi{
vector<int>adj[100100],adj2[100100];
bitset<100100>vis;
int col[100100],CCcol,depdep=0,depnod,par[100100],deepest_path[100100];
void dfstree(int n){
vis[n]=1;
for(auto i:adj[n]){
if(!vis[i]) {
dfstree(i);
adj2[i].push_back(n);
adj2[n].push_back(i);
}
}
}
void getdeepest(int n,int dep){
if(dep>depdep)
depdep=dep,depnod=n;
for(auto i:adj2[n])
if(!col[i]&&i-par[n])
getdeepest(i,dep+1);
}
void gowild(int n,int&CC,int color){
if(!CC)return;
if(!col[n])CC--,col[n]=color;
for(auto i:adj2[n])
if(i-par[n]&&(!col[i]||col[i]==color))
gowild(i,CC,color);
}
void assigncols(int rt,int thecol){
depdep=0;
int CC=60;
getdeepest(rt,1);
deepest_path[rt]=1;
int C=depnod;
while(C-rt) deepest_path[C]=1,
CC--,col[C]=thecol,C=par[C];
gowild(rt,CC,thecol);
}
void preproc(int n,int p){
par[n]=p;
for(auto i:adj2[n])
if(i-p)preproc(i,n);
}
void makenocol(int n){
col[n]=-1;
for(auto i:adj2[n])
if(i-par[n]&&!col[i])
makenocol(i);
}
int dfscol(int n){
int sz=1;
for(auto i:adj2[n])
if(i-par[n])
sz+=dfscol(i);
if(sz>=60)
assigncols(n,++CCcol),sz=0;
if(n==1&&sz){
makenocol(n);
}
return sz;
}
void tofindall(int n){
for(auto i:adj2[n])
if(col[i]==col[n]&&!deepest_path[i]&&i!=par[n])
gooo(i),tofindall(i);
if(!deepest_path[n])
gooo(par[n]);
else for(auto i:adj2[n])
if(i-par[n]&&deepest_path[i]&&col[i]==col[n])
gooo(i),tofindall(i);
}
pair<int,int>getclos(int n){
if(col[n]>0)return{0,n};
pair<int,int>ans={100100,0};
for(auto i:adj2[n])
if(i!=par[n])
ans=min(ans,getclos(i));
return {ans.first+1,ans.second};
}
}
long long Ioi2(int P,int N){
auto[x,y]=ioi::getclos(P);
vector<int>path;
do{
path.push_back(y);
y=ioi::par[y];
}while(y-P);
reverse(path.begin(),path.end());
for(auto i:path)
gooo(P=i);
ioi::tofindall(P);
vector<int>important;
for(int i=1;i<=N;i++)
if(ioi::col[i]==ioi::col[P])
important.push_back(i);
long long ans=0;
reverse(important.begin(),important.end());
for(auto i:important)
ans=ans<<1|messg[i];
return ans;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i=1;i<=N;i++)
ioi::adj[i].clear(),ioi::adj2[i].clear();
for(int i=0;i<M;i++)
ioi::adj[A[i]+1].push_back(B[i]+1),
ioi::adj[B[i]+1].push_back(A[i]+1);
P++;
messg[P]=V;
ioi::dfstree(1);
ioi::preproc(1,0);
ioi::dfscol(1);
assert(ioi::vis.count()==N);
assert(ioi::CCcol>=1);
for(int i=2;i<=N;i++)
if(!ioi::par[i])
return 34;
if(ioi::col[P]==-1){
return Ioi2(P,N);
}
while(!ioi::col[P])
gooo(P=ioi::par[P]);
while(ioi::col[ioi::par[P]]==ioi::col[P])
gooo(P=ioi::par[P]);
ioi::tofindall(P);
vector<int>important;
for(int i=1;i<=N;i++)
if(ioi::col[i]==ioi::col[P])
important.push_back(i);
long long ans=0;
reverse(important.begin(),important.end());
for(auto i:important)
ans=(ans<<1)|messg[i];
return ans;
}
Compilation message
Joi.cpp: In function 'void gooo(int)':
Joi.cpp:6:16: error: 'Move' was not declared in this scope
6 | messg[nod]=Move(nod-1);
| ^~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Joi.cpp:2:
Joi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Joi.cpp:122:28: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
122 | assert(ioi::vis.count()==N);
| ~~~~~~~~~~~~~~~~^~~
/usr/bin/ld: /tmp/ccnGCFur.o: in function `main':
grader_ioi.cpp:(.text.startup+0x3f2): undefined reference to `Ioi(int, int, int*, int*, int, int, int)'
collect2: error: ld returned 1 exit status
