#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
namespace joi{
vector<int>adj[10010],adj2[10010];
bitset<10010>vis,inthisblok,deepest_path;
int col[10010],CCcol,depdep=0,depnod,par[10010];
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:adj[n])
if(!col[i]&&i-par[n])
getdeepest(i,dep+1);
}
void gowild(int n,int&CC,int color){
if(!col[n])CC--,col[n]=color;
if(!CC)return;
for(auto i:adj[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:adj[n])
if(i-p)preproc(i,n);
}
int dfscol(int n){
int sz=1;
for(auto i:adj[n])
if(i-par[n])
sz+=dfscol(i);
if(sz>=60)
assigncols(n,++CCcol),sz=0;
return sz;
}
}
vector<int>positions[10010];
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[10010],adj2[10010];
bitset<10010>vis,inthisblok,aroot;
int col[10010],CCcol,depdep=0,depnod,par[10010],deepest_path[10010];
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:adj[n])
if(!col[i]&&i-par[n])
getdeepest(i,dep+1);
}
void gowild(int n,int&CC,int color){
if(!col[n])CC--,col[n]=color;
if(!CC)return;
for(auto i:adj[n])
if(i-par[n]&&(!col[i]||col[i]==color))
gowild(i,CC,color);
}
void assigncols(int rt,int thecol){
aroot[rt]=1;
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:adj[n])
if(i-p)preproc(i,n);
}
void makenocol(int n){
col[n]=-1;
for(auto i:adj[n])
if(i-par[n]&&!col[i])
makenocol(i);
}
int dfscol(int n){
int sz=1;
for(auto i:adj[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:adj[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:adj[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={1e9,1e9};
for(auto i:adj[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=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);
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2064 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2080 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2092 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2072 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2080 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2068 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2080 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2084 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2080 KB |
Output is correct |
| 10 |
Runtime error |
213 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
171 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2064 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2064 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2068 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2624 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2628 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2620 KB |
Output is correct |
| 9 |
Correct |
12 ms |
5688 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5696 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5688 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2064 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2080 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2080 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2068 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
227 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
205 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
