Submission #163275

#TimeUsernameProblemLanguageResultExecution timeMemory
163275HungAnhGoldIBO2020Unique Cities (JOI19_ho_t5)C++14
0 / 100
399 ms46328 KiB
#include<bits/stdc++.h> using namespace std; const int N=2e5+2; const int LOG=19; int ar[N]; int ans[N][2],pts[2],level[N][2],ancestor[N][LOG][2],cnt=0; bool used[N][2]; //int pos[N]; //set<int> color[N]; set<int> color; vector<int> lis[N],adj[N]; void dfs(int x,int p){ if(cnt<2){ if(level[x][0]>=level[pts[cnt]][0]){ pts[cnt]=x; } } lis[level[x][0]].push_back(x); for(int i=0;i<adj[x].size();i++){ if(adj[x][i]!=p){ level[adj[x][i]][0]=level[x][0]+1; dfs(adj[x][i],x); } } } void dfs1(int x,int p){ //right now cnt is above int idx=0,i; for(i=1;i<LOG;i++){ ancestor[x][i][cnt]=ancestor[ancestor[x][i-1][cnt]][i-1][cnt]; } for(i=0;i<adj[x].size();i++){ if(adj[x][i]!=p){ level[adj[x][i]][cnt]=level[x][cnt]+1; ancestor[adj[x][i]][0][cnt]=x; dfs1(adj[x][i],x); // if(color[pos[adj[x][i]]].size()>color[idx].size()){ // idx=pos[adj[x][i]]; // } } } // pos[x]=idx; // for(i=0;i<adj[x].size();i++){ // if(adj[x][i]!=p&&pos[adj[x][i]]!=idx){ // for(auto ite=color[pos[adj[x][i]]].begin();ite!=color[pos[adj[x][i]]].end();ite++){ // color[pos[x]].insert(*ite); // } // } // } // ans[x][cnt]=color[pos[x]].size(); // if(used[x][cnt]){ // color[pos[x]].insert(ar[x]); // } } int findd(int x,int k,int idx){ while(k){ int y=__lg(k); x=ancestor[x][y][idx]; k-=(1<<y); } return x; } int LCA(int x,int y,int idx){ if(level[x][idx]>level[y][idx]){ x=findd(x,level[x][idx]-level[y][idx],idx); } y=findd(y,level[y][idx]-level[x][idx],idx); if(x==y){ return x; } for(int i=LOG-1;i>=0;i--){ if(ancestor[x][i][idx]!=ancestor[y][i][idx]){ x=ancestor[x][i][idx],y=ancestor[y][i][idx]; } } return ancestor[x][0][idx]; } int dis(int x,int y){ return level[x][0]+level[y][0]-2*level[LCA(x,y,0)][0]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m,i,j,k,l; cin>>n>>m; for(i=1;i<n;i++){ cin>>j>>k; adj[j].push_back(k); adj[k].push_back(j); } for(i=1;i<=n;i++){ cin>>ar[i]; } dfs(1,1); cnt++; level[pts[0]][0]=0; for(i=0;i<n;i++){ lis[i].clear(); } //this maybe confusing ofter, but... it's ok because level using dfs is 0 dfs(pts[0],pts[0]); for(i=0;i<n;i++){ if(lis[i].size()==1){ used[lis[i][0]][0]=true; // cout<<lis[i][0]<<' '; } lis[i].clear(); } // cout<<endl; level[pts[1]][0]=0; cnt++; dfs(pts[1],pts[1]); for(i=0;i<n;i++){ if(lis[i].size()==1){ used[lis[i][0]][1]=true; } lis[i].clear(); } level[pts[0]][0]=0; cnt=0; dfs1(pts[0],pts[0]); j=pts[1]; while(j){ ans[j][0]=color.size(); if(used[j][0]){ color.insert(ar[j]); } j=ancestor[j][0][0]; } // for(i=1;i<=n;i++){ // cout<<ans[i][cnt]<<' '; // } // cout<<endl; cnt++; // for(i=0;i<n;i++){ // color[i].clear(); // } level[pts[1]][1]=0; dfs1(pts[1],pts[1]); color.clear(); j=pts[0]; while(j){ ans[j][1]=color.size(); if(used[j][1]){ color.insert(ar[j]); } j=ancestor[j][0][1]; } // for(i=1;i<=n;i++){ // cout<<ans[i][cnt]<<' '; // } // cout<<endl; // cout<<dis(1,5)<<endl; for(i=1;i<=n;i++){ j=dis(i,pts[0]); k=dis(i,pts[1]); if(j==k){ cout<<0<<'\n'; continue; } if(j<k){ // cout<<findd(pts[1],k-j,0)<<" cac\n"; cout<<ans[findd(pts[1],k-j,0)][0]<<'\n'; } else{ // cout<<findd(pts[0],j-k,1)<<" cac\n"; cout<<ans[findd(pts[0],j-k,1)][1]<<'\n'; } } }

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void dfs1(int, int)':
joi2019_ho_t5.cpp:31:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<adj[x].size();i++){
          ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:27:6: warning: unused variable 'idx' [-Wunused-variable]
  int idx=0,i;
      ^~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:83:16: warning: unused variable 'l' [-Wunused-variable]
  int n,m,i,j,k,l;
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...