Submission #1118570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118570		pera	Traffickers (RMI18_traffickers)	C++17	100 / 100	1604 ms	159768 KiB

traffickers

#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin >> n;
   vector<vector<int>> g(n + 1);
   for(int i = 1;i < n;i ++){
      int u , v;
      cin >> u >> v;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
   }
   int timer = 0;
   const int LOG = 15;
   vector<int> in(n + 1) , out(n + 1) , d(n + 1);
   vector<vector<int>> up(n + 1 , vector<int>(LOG));
   function<void(int , int)> dfs = [&](int u , int p){
      up[u][0] = p;
      d[u] = d[p] + 1;
      in[u] = ++timer;
      for(int v : g[u]){
         if(v != p){
            dfs(v , u);
         }
      }
      out[u] = timer;
   };
   dfs(1 , 1);
   for(int bit = 1;bit < LOG;bit ++){
      for(int u = 1;u <= n;u ++){
         up[u][bit] = up[up[u][bit - 1]][bit - 1];
      }
   }
   auto lca = [&](int u , int v){
      if(d[u] < d[v]){
         swap(u , v);
      }
      for(int bit = 0;bit < LOG;bit ++){
         if((d[u] - d[v]) >> bit & 1){
            u = up[u][bit];
         }
      }
      if(u == v){
         return u;
      }
      for(int bit = LOG - 1;bit >= 0;bit --){
         if(up[u][bit] != up[v][bit]){
            u = up[u][bit];
            v = up[v][bit];
         }
      }
      return up[u][0];
   };
   auto dist = [&](int u , int v){
      return d[u] + d[v] - 2 * d[lca(u , v)] + 1;
   };
   const int L = 20;
   vector<vector<vector<int>>> f(n + 1 , vector<vector<int>>(L + 1 , vector<int>(L + 1)));
   vector<vector<vector<int>>> val(n + 1 , vector<vector<int>>(L + 1 , vector<int>(L + 1)));
   auto join = [&](vector<vector<int>> &x , vector<vector<int>> a){
      for(int i = 1;i <= L;i ++){
         for(int j = 1;j <= L;j ++){
            x[i][j] += a[i][j];
         }
      }
   };
   auto update = [&](int i , int x , int y , int w){
      while(i <= n){
         f[i][x][y] += w;
         i += i&-i;
      }
   };
   auto query = [&](int i){
      vector<vector<int>> cnt(L + 1 , vector<int>(L + 1));
      while(i > 0){
         join(cnt , f[i]);
         i -= i&-i;
      }
      return cnt;
   };
   auto calc = [&](int u , int v){
      auto eu = query(in[u]);
      auto ev = query(in[v]);
      int _lca = lca(u , v);
      auto eL = query(in[_lca]);
      for(int i = 1;i <= L;i ++){
         for(int j = 1;j <= L;j ++){
            eL[i][j] *= -2;
         }
      }
      join(eu , eL);
      join(eu , ev);
      join(eu , val[_lca]);
      return eu;
   };
   auto UPD = [&](int u , int sz , int c , int w){
      val[u][sz][c] += w;
      update(in[u] , sz , c , w);
      if(out[u] < n){
         update(out[u] + 1 , sz , c , -w);
      }
   };
   auto upd = [&](int u , int v , int w){
      int _lca = lca(u , v) , sz = dist(u , v);
      int _u = u , c = 1;
      while(_u != _lca){
         UPD(_u , sz , c , w);
         ++c;
         _u = up[_u][0];
      }
      c = sz;
      int _v = v;
      while(_v != _lca){
         UPD(_v , sz , c , w);
         --c;
         _v = up[_v][0];
      }
      UPD(_lca , sz , c , w);
   };
   auto get = [&](vector<vector<int>> cnt , int t){
      long long s = 0LL;
      for(int i = 1;i <= L;i ++){
         for(int j = 1;j <= L;j ++){
            s += 1LL * (t / i) * cnt[i][j] + 1LL * (t % i >= j) * cnt[i][j];
         }
      }
      return s;
   };
   int K;
   cin >> K;
   while(K--){
      int u , v;
      cin >> u >> v;
      upd(u , v , +1);
   }
   int Q;
   cin >> Q;
   while(Q--){
      int ty;
      cin >> ty;
      if(ty == 1){
         int u , v;
         cin >> u >> v;
         upd(u , v , +1);
      }else if(ty == 2){
         int u , v;
         cin >> u >> v;
         upd(u , v , -1);
      }else{
         int u , v , t1 , t2;
         cin >> u >> v >> t1 >> t2;
         auto e = calc(u , v);
         ++t2,++t1;
         cout << get(e , t2) - (t1 > 0 ? get(e , t1 - 1) : 0LL) << '\n';
      }
   }
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40