제출 #1027146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027146		pera	Two Currencies (JOI23_currencies)	C++17	0 / 100	17 ms	38748 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) , bound(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] = 1 , 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]);
      ans[i] = X[i] - (D[S[i]] + D[T[i]] - 2 * D[LCA[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];
   });
   for(int bit = LOG - 1;bit >= 0;bit --){
      vector<vector<int>> query(n + 1);
      for(int i = 1;i <= q;i ++){
         if(bound[i] + (1 << bit) <= m){
            query[bound[i] + (1 << bit)].push_back(i);
         }
      }
      vector<int>(n + 1).swap(t);
      vector<int>(n + 1).swap(o);
      for(int i = 1;i <= m;i ++){
         int v = P[order[i]];
         upd(in[v] , C[order[i]]);
         upd(out[v] + 1 , -C[order[i]]);
         for(int id : query[i]){
            int silver_cost = GET(in[S[id]]) + GET(in[T[id]]) - 2 * GET(in[LCA[id]]);
            int gold_cost = get(in[S[id]]) + get(in[T[id]]) - 2 * get(in[LCA[id]]);
            if(silver_cost <= Y[id]){
               bound[id] = i;
               ans[id] = X[id] - (D[S[id]] + D[T[id]] - 2 * D[LCA[id]] - gold_cost);
            }
         }
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << max(ans[i] , -1LL) << endl;
   }
}
/*
3
6
6
7
7
3
1
2
2
*/

컴파일 시 표준 에러 (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