| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 78374 | nxteru | Amusement Park (JOI17_amusement_park) | C++14 | 0 ms | 0 KiB |
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 "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
int nj,mj[60],parj[10005],wj[10005],kj,Sj[60],Oj[60],PAj;
ll anj[60];
bool Ej[60][60];
vector<int>gj[10005];
int findj(int x){
if(x==parj[x])return x;
return parj[x]=findj(parj[x]);
}
bool samej(int x,int y){return findj(x)==findj(y);}
void unitj(int x,int y){parj[findj(x)]=findj(y);}
void dfs1j(int v,int p){
Oj[k]=v;
wj[v]=kj++;
if(p!=-1){
Ej[wj[v]][wj[p]]=true;
Ej[wj[p]][wj[v]]=true;
Sj[wj[v]]++;
Sj[wj[p]]++;
}
if(kj==60)return;
for(int i=0;i<gj[v].size();i++){
int u=gj[v][i];
if(u!=p)dfs1j(u,v);
}
}
void dfs2j(int v,int l,int p,int o[60],bool e[60][60],int s[60]){
if(wj[v]!=-1){
for(int i=0;i<gj[v].size();i++){
int u=gj[v][i];
if(u!=p){
dfs2j(u,wj[v],v,o,e,s);
}
}
return;
}
int r;
for(int i=0;i<60;i++){
if(s[i]==1&&o[i]!=p){
r=i;
break;
}
}
for(int i=0;i<60;i++){
e[r][i]=false;
e[i][r]=false;
}
w[v]=r;
o[r]=v;
e[r][l]=true;
e[l][r]=true;
s[l]++;
for(int i=0;i<gj[v].size();i++){
int u=gj[v][i];
if(u!=p){
dfs2j(u,wj[v],v,o,e,s);
}
}
}
void Joi(int N,int M,int A[],int B[],ll X,int t){
nj=N;
for(int i=0;i<nj;i++){
parj[i]=i;
wj[i]=-1;
}
for(int i=0;i<M;i++){
if(!samej(A[i],B[i])){
gj[A[i]].PB(B[i]);
gj[B[i]].PB(A[i]);
unitj(A[i],B[i]);
}
}
for(int i=0;i<60;i++)mj[i]=(X>>i)&1;
dfs1j(0,-1);
dfs2j(0,wj[0],-1,Oj,Ej,Sj);
for(int i=0;i<nj;i++){
MessageBoard(i,mj[wj[i]]);
}
}
