fork download
copy 
  1. // Kirito's official solution to year2018p6 - Old Christmas Lights II
  2. #include<bits/stdc++.h>
  3. const int MAXN=5e4+4,MAXQ=5e4+4,RT=800,MAXLN=18,INF=0x3f3f3f3f;
  4. int N,Q,cnt,C[MAXN],depth[MAXN],ans[MAXN],ein[MAXN],eout[MAXN],eid[MAXN<<1],st[MAXN][MAXLN];
  5. struct qry {
  6.     int l,r,lca,i;
  7.     bool operator <(const qry &q) const {
  8.         return l/RT<q.l/RT||(l/RT==q.l/RT&&r<q.r);
  9.     }
  10. }qrys[MAXQ];
  11. std::vector<int>adj[MAXN];
  12. std::multiset<int>S,diff;
  13. std::bitset<MAXN>seen;
  14. void dfs(int src,int p,int d=1) {
  15.     eid[ein[src]=++cnt]=src;
  16.     st[src][0]=p;
  17.     depth[src]=d++;
  18.     for(int i:adj[src]) {
  19.         if(i==p) continue;
  20.         dfs(i,src,d);
  21.     }
  22.     eid[eout[src]=++cnt]=src;
  23. }
  24. inline void build() {
  25.     for(int j=1;j<MAXLN;++j)
  26.         for(int i=1;i<=N;++i)
  27.             if(~st[i][j-1])
  28.                 st[i][j]=st[st[i][j-1]][j-1];
  29.             else
  30.                 st[i][j]=-1;
  31. }
  32. inline int lca(int a,int b) {
  33.     if(depth[a]<depth[b]) std::swap(a,b);
  34.     for(int i=MAXLN-1;i>=0;--i)
  35.         if(~st[a][i]&&depth[st[a][i]]>=depth[b])
  36.             a=st[a][i];
  37.     if(a==b) return a;
  38.     for(int i=MAXLN-1;i>=0;--i)
  39.         if(st[a][i]!=st[b][i])
  40.             a=st[a][i],b=st[b][i];
  41.     return st[a][0];
  42. }
  43. inline void moUpd(int t){
  44.     seen.flip(t);
  45.     if(seen[t]){
  46.         if(S.size()==1)
  47.             diff.insert(abs(C[t]-*S.begin()));
  48.         else if(S.size()>1) {
  49.             auto x=S.lower_bound(C[t]);
  50.             if(x==S.begin())
  51.                 diff.insert(*x-C[t]);
  52.             else {
  53.                 auto y=std::prev(x);
  54.                 if(x==S.end())
  55.                     diff.insert(C[t]-*y);
  56.                 else{
  57.                     diff.erase(diff.lower_bound(*x-*y));
  58.                     diff.insert(C[t]-*y);
  59.                     diff.insert(*x-C[t]);
  60.                 }
  61.             }
  62.         }
  63.         S.insert(C[t]);
  64.     }else{
  65.         S.erase(S.find(C[t]));
  66.         if(S.size()==1)
  67.             diff.erase(diff.lower_bound(abs(C[t]-*S.begin())));
  68.         else if(S.size()>1) {
  69.             auto x=S.lower_bound(C[t]);
  70.             if(x==S.begin())
  71.                 diff.erase(diff.lower_bound(*x-C[t]));
  72.             else {
  73.                 auto y=std::prev(x);
  74.                 if(x==S.end())
  75.                     diff.erase(diff.lower_bound(C[t]-*y));
  76.                 else{
  77.                     diff.insert(*x-*y);
  78.                     diff.erase(diff.lower_bound(C[t]-*y));
  79.                     diff.erase(diff.lower_bound(*x-C[t]));
  80.                 }
  81.             }
  82.         }
  83.     }
  84. }
  85. int main() {
  86.     assert(scanf("%d%d",&N,&Q)==2);
  87.     for(int i=1;i<=N;assert(scanf("%d",C+i++)==1));
  88.     for(int i=1,a,b;i<N;++i) {
  89.         assert(scanf("%d%d",&a,&b)==2);
  90.         adj[a].emplace_back(b);
  91.         adj[b].emplace_back(a);
  92.     }
  93.     dfs(1,-1);
  94.     build();
  95.     for(int i=0,a,b,l;i<Q;++i) {
  96.         assert(scanf("%d%d",&a,&b)==2);
  97.         l=lca(a,b);
  98.         if(ein[a]>ein[b]) std::swap(a,b);
  99.         if(a==l||b==l)
  100.             qrys[i]={ein[a],ein[b],-1,i};
  101.         else
  102.             qrys[i]={eout[a],ein[b],C[l],i};
  103.     }
  104.     std::sort(qrys,qrys+Q);
  105.     for(int i=0,l=0,r=0,lst=-1;i<Q;++i) {
  106.         if(lst!=qrys[i].l/RT) {
  107.             S.clear();
  108.             diff.clear();
  109.             seen.reset();
  110.             moUpd(eid[l=r=qrys[i].l]);
  111.             lst=qrys[i].l/RT;
  112.         }
  113.         while(r<qrys[i].r)
  114.             moUpd(eid[++r]);
  115.         while(l>qrys[i].l)
  116.             moUpd(eid[--l]);
  117.         while(l<qrys[i].l)
  118.             moUpd(eid[l++]);
  119.         while(r>qrys[i].r)
  120.             moUpd(eid[r--]);
  121.         ans[qrys[i].i]=*diff.begin();
  122.         if(~qrys[i].lca) {
  123.             if(S.size()==1)
  124.                 ans[qrys[i].i]=std::min(ans[qrys[i].i],abs(qrys[i].lca-*S.begin()));
  125.             else if(S.size()>1) {
  126.                 auto x=S.lower_bound(qrys[i].lca);
  127.                 int oth=INF;
  128.                 if(x==S.begin())
  129.                     oth=*x-qrys[i].lca;
  130.                 else {
  131.                     auto y=std::prev(x);
  132.                     if(x==S.end())
  133.                         oth=qrys[i].lca-*y;
  134.                     else
  135.                         oth=std::min(*x-qrys[i].lca,qrys[i].lca-*y);
  136.                 }
  137.                 ans[qrys[i].i]=std::min(ans[qrys[i].i],oth);
  138.             }
  139.         }
  140.     }
  141.     for(int i=0;i<Q;printf("%d\n",ans[i++]));
  142. }
Runtime error #stdin #stdout #stderr 0s 4536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:86: int main(): Assertion `scanf("%d%d",&N,&Q)==2' failed.
https://ideone.com/OSlWJN
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!