Submission #1032745

#TimeUsernameProblemLanguageResultExecution timeMemory
1032745boyliguanhanAmusement Park (JOI17_amusement_park)C++17
73 / 100
20 ms16092 KiB
#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={1e9,1e9}; 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==1e9)return 9; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...