Submission #1027131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027131		pera	Two Currencies (JOI23_currencies)	C++17	0 / 100	19 ms	38012 KiB

currencies

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 1 , LOG = 22;
int n , m , q , e = 0;
vector<int> LCA(N) , t(N) , D(N) , o(N) , U(N) , V(N) , ans(N) , L(N) , R(N) , P(N) , C(N) , S(N) , T(N) , X(N) , Y(N) , in(N) , out(N) , d(N);
vector<vector<int>> g(N) , up(N , vector<int>(LOG));
vector<int> order = {0};
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){
   int 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 = 1){
   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(){
   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];
   }
   for(int i = 1;i <= q;i ++){
      cin >> S[i] >> T[i] >> X[i] >> Y[i];
      L[i] = 0 , R[i] = m;
      ans[i] = -1;
   }
   dfs(1);
   for(int i = 1;i <= m;i ++){
      if(d[U[i]] < d[V[i]]){
         swap(U[i] , V[i]);
      }
      ++D[U[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]);
   }
   for(int i = 1;i <= m;i ++){
      order.push_back(i);
   }
   sort(order.begin() + 1 , order.end() , [&](int x , int y){
      return C[x] < C[y];
   });
   int E = 1;
   while(E){
      E = 0;
      vector<int>(n + 1).swap(t);
      vector<int>(n + 1).swap(o);
      vector<vector<int>> query(n + 1);
      for(int i = 1;i <= q;i ++){
         if(L[i] <= R[i]){
            query[(L[i] + R[i]) / 2].push_back(i);
            E = 1;
         }
      }
      for(int x = 0;x <= m;x ++){
         if(x > 0){
            int v = P[order[x]];
            upd(in[v] , C[order[x]]);
            upd(out[v] + 1 , -C[order[x]]);
         }
         for(int id : query[x]){
            int cost_silver = GET(in[S[id]]) + GET(in[T[id]]) - 2 * GET(in[LCA[id]]);
            int h = get(in[S[id]]) + get(in[T[id]]) - 2 * get(in[LCA[id]]);
            if(cost_silver <= Y[id]){
               ans[id] = X[id] - (D[S[id]] + D[T[id]] - 2 * D[LCA[id]] - h);
               L[id] = x + 1;
            }else{
               R[id] = x - 1;
            }
         }
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << max(ans[i] , -1LL) << endl;
   }
}

Compilation message (stderr)

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

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