#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
namespace joi{
vector<int>adj[100100],adj2[100100];
bitset<100100>vis,inthisblok,deepest_path;
int col[100100],CCcol,depdep=0,depnod,par[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);
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);
}
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;
return sz;
}
}
vector<int>positions[10100];
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i=0;i<M;i++)
joi::adj[A[i]+1].push_back(B[i]+1),
joi::adj[B[i]+1].push_back(A[i]+1);
joi::dfstree(1);
joi::preproc(1,0);
joi::dfscol(1);
for(int i=1;i<=N;i++) if(joi::col[i])
positions[joi::col[i]].push_back(i);
for(int i=1;i<=joi::CCcol;i++){
long long X2=X;
for(auto j:positions[i])
MessageBoard(j-1,X2&1),X2>>=1;
}
for(int i=1;i<=N;i++) if(!joi::col[i])
MessageBoard(i-1,0);
}
#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);
}
}
adj[n].clear();
}
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;
if(y==0) return 6;
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++;
for(int i=2;i<=N;i++)
if(!ioi::par[i])
return 34;
messg[P]=V;
ioi::dfstree(1);
ioi::preproc(1,0);
ioi::dfscol(1);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10268 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
13408 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10264 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
13420 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
13420 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
