Submission #1196803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196803		loom	Roadside Advertisements (NOI17_roadsideadverts)	C++20	100 / 100	63 ms	35400 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

const int N = 5e4+1, lg = 17;
vector<pair<int,int>> g[N];
int mn[2*N][lg], ix[2*N][lg];
int in[N], dep[N];
int cnt;

void dfs(int v, int p){
   in[v] = cnt;
   mn[cnt][0] = in[v];
   ix[cnt][0] = v;
   cnt++;

   for(auto [ch, w] : g[v]){
      if(ch == p) continue;
      
      dep[ch] = dep[v]+w;
      dfs(ch, v);

      mn[cnt][0] = in[v];
      ix[cnt][0] = v;
      cnt++;
   }
}

void precomp(){
   dfs(0, -1);

   for(int j=1; j<lg; j++){
      for(int i=0; i+(1<<j)-1 < 2*N; i++){
         int l = mn[i][j-1], r = mn[i+(1<<(j-1))][j-1];
         
         mn[i][j] = min(l, r);
         ix[i][j] = (l <= r ? ix[i][j-1] : ix[i+(1<<(j-1))][j-1]);
      }
   }
}

int lca(int x, int y){
   x = in[x];
   y = in[y];
   if(x > y) swap(x, y);

   int lg = log2(y-x+1);
   return (mn[x][lg] <= mn[y-(1<<lg)+1][lg] ? ix[x][lg] : ix[y-(1<<lg)+1][lg]);
}

int dis(int x, int y){
   return dep[y] - dep[x];
}

inline void solve(){
   int n;
   cin>>n;
   for(int i=1; i<n; i++){
      int a, b, w;
      cin>>a>>b>>w;
      g[a].push_back({b, w});
      g[b].push_back({a, w});
   }
   precomp();

   int q;
   cin>>q;
   while(q--){
      vector<int> v(5);
      for(int &i : v) cin>>i;

      int rt = v[0];
      for(int i=1; i<5; i++) rt = lca(rt, v[i]);

      int ans = dis(rt, v[0]);
      for(int i=1; i<5; i++){
         int mn = 1e18;
         for(int j=0; j<i; j++){
            mn = min(mn, dis(lca(v[j], v[i]), v[i]));
         }
         ans += mn;
      }

      cout<<ans<<nl;
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30