| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1032759 | vjudge1 | Amusement Park (JOI17_amusement_park) | C++17 | 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 "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
void deassert(int n){
if(!n)Move(-1);
}
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);
}
int frm[100100];
vector<int>getclos(int n){
vis.reset();
vis[n]=1;
queue<int>q;
q.push(n);
int ANS;
while(1){
int x=q.front();
q.pop();
if(col[x]>0){
ANS=x;
break;
}
for(auto i:adj[x])
if(!vis[i])vis[i]=1,
frm[i]=x,q.push(i);
}
vector<int>ans;
while(ANS-n)
ans.push_back(ANS),ANS=frm[ANS];
reverse(ans.begin(),ans.end());
return ans;
}
}
long long Ioi2(int P,int N){
vector<int>path=ioi::getclos(P);
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);
deassert(ioi::vis.count()==N);
deassert(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;
}