Submission #1028422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028422		pera	Two Currencies (JOI23_currencies)	C++17	100 / 100	677 ms	46280 KiB

currencies

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 1 , LOG = 18;
int n , m , q , e = 0;
int LCA[N] , bound[N] , D[N] , o[N] , U[N] , V[N] , P[N] , d[N] , S[N] , T[N] , X[N] , Y[N] , in[N] , out[N] , up[N][LOG];
long long t[N] , ans[N] , C[N];
vector<int> g[N];
vector<pair<int , int>> order; 
void upd(int u , int x){
   while(u <= n){
      t[u] += x;
      o[u] += (x > 0 ? 1 : -1);
      u += u&-u;
   }
}
int GET(int u){
   long long sum = 0;
   while(u > 0){
      sum += t[u];
      u -= u&-u;
   }
   return sum;
}
int get(int u){
   int sum = 0;
   while(u > 0){
      sum += o[u];
      u -= u&-u;
   }
   return sum;
}
void dfs(int u ,  int p = 1){
   in[u] = ++e;
   up[u][0] = p;
   d[u] = d[p] + 1;
   for(int x = 0;x < (int)g[u].size();x ++){
      if(g[u][x] != p){
         dfs(g[u][x] , u);
      }
   }
   out[u] = e;
}
void DFS(int u , int p = 0){
   D[u] += D[p];
   for(int x = 0;x < (int)g[u].size();x ++){
      if(g[u][x] != p){
         DFS(g[u][x] , u);
      }
   }
}
int lca(int u , int v){
   if(d[u] < d[v]){
      swap(u , v);
   }
   int s = d[u] - d[v];
   for(int bit = 0;bit < LOG;bit ++){
      if(s >> 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];
}
main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin >> n >> m >> q;
   for(int i = 1;i < n;i ++){
      cin >> U[i] >> V[i];
      g[U[i]].push_back(V[i]);
      g[V[i]].push_back(U[i]);
   }
   for(int i = 1;i <= m;i ++){
      cin >> P[i] >> C[i];
      order.push_back({C[i] , i});
   }
   sort(order.begin() , order.end());
   for(int i = 1;i <= q;i ++){
      cin >> S[i] >> T[i] >> X[i] >> Y[i];
      ans[i] = -1;
   }
   dfs(1);
   for(int i = 1;i <= m;i ++){
      if(d[U[P[i]]] < d[V[P[i]]]){
         swap(U[P[i]] , V[P[i]]);
      }
      ++D[U[P[i]]];
   }
   DFS(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];
      }
   }
   for(int i = 1;i <= q;i ++){
      LCA[i] = lca(S[i] , T[i]);
      ans[i] = X[i] - (D[S[i]] + D[T[i]] - 2 * D[LCA[i]]);
   }
   for(int bit = LOG - 1;bit >= 0;bit --){
      vector<int> query[m + 1];
      for(int i = 1;i <= q;i ++){
         if(bound[i] + (1 << bit) <= m){
            query[bound[i] + (1 << bit)].push_back(i);
         }
      }
      for(int i = 1;i <= n;i ++){
         o[i] = 0;
         t[i] = 0LL;
      }
      for(int x = 1;x <= m;x ++){
         int g = order[x - 1].second;
         upd(in[U[P[g]]] , C[g]);
         upd(out[U[P[g]]] + 1 , -C[g]);
         for(int id : query[x]){
            long long silver = GET(in[S[id]]) + GET(in[T[id]]) - 2 * GET(in[LCA[id]]);
            int gold = get(in[S[id]]) + get(in[T[id]]) - 2 * get(in[LCA[id]]);
            if(silver <= Y[id]){
               ans[id] = X[id] - (D[S[id]] + D[T[id]] - 2 * D[LCA[id]]) + gold;
               bound[id] = x;
            }
         }
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << max(ans[i] , -1LL) << endl;
   }
}

Compilation message (stderr)

currencies.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32