Submission #842798

#	Time	Username	Problem	Language	Result	Execution time	Memory
842798		eltu0815	Two Currencies (JOI23_currencies)	C++14	100 / 100	4818 ms	75316 KiB

currencies

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define MAXN 101010
using namespace std;

typedef long long ll;

int N, M, Q;
int parent[20][MAXN];
int depth[MAXN];
int in[MAXN], out[MAXN];
int max_height;
int dfs_ordering[MAXN];
vector<int> adj[MAXN];

typedef struct save_points {
   ll s, e, val;
   bool operator < (const save_points& right) {
      return val < right.val;
   }
} save_points;

typedef struct Query {
   ll s, t, x, y;
} Query;

vector<save_points> SP;
vector<Query> queries;
int l[MAXN], r[MAXN];
vector< pair<int, int> > roads;

void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); }

void input() {
   cin >> N >> M >> Q;
   roads.resize(N);
   for (int i = 1; i <= N - 1; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
      roads[i] = { min(a, b), max(a, b) };
   }
   for (int i = 1; i <= M; i++) {
      int a, b;
      cin >> a >> b;
      save_points tmp = { roads[a].first, roads[a].second, b };
      SP.push_back(tmp);
   }
   sort(SP.begin(), SP.end());
   queries.resize(Q);
   for (int i = 0; i < Q; i++)
      cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
}

int Euler_tour_idx, ordering_idx;

void Euler_tour(int n, int dep) { // set in, out, depth, parent
   dfs_ordering[n] = ++ordering_idx;
   in[n] = ++Euler_tour_idx;
   depth[n] = dep;
   for (int i = 0; i < adj[n].size(); i++) {
      int next = adj[n][i];
      if (in[next]) continue;
      parent[0][next] = n;
      Euler_tour(next, dep + 1);
   }
   ++Euler_tour_idx;
   out[n] = Euler_tour_idx;
}

void set_parent() { // for faster lca
   int tmp = N, cnt = 0;
   while (tmp > 1) {
      tmp >>= 1;
      cnt++;
   }
   max_height = cnt;
   for (int k = 1; k <= max_height; k++)
      for (int i = 2; i <= N; i++)
         if (parent[k - 1][i])
            parent[k][i] = parent[k - 1][parent[k - 1][i]];
}

int LCA(int a, int b) { // returns lca of node a and b
   if (depth[a] != depth[b]) {
      if (depth[a] < depth[b]) swap(a, b); // a is deeper
      ll dif = depth[a] - depth[b];
      for (ll i = 0; dif > 0; i++) {
         if (dif & 1) a = parent[i][a];
         dif >>= 1;
      }
   }

   if (a != b) {
      for (int k = max_height; 0 <= k; k--) {
         if (parent[k][a] != 0 && parent[k][a] != parent[k][b]) {
            a = parent[k][a];
            b = parent[k][b];
         }
      }
      a = parent[0][a];
   }

   return a;
}

ll tree1[8 * MAXN], tree2[8 * MAXN], tree3[8 * MAXN];

void update(ll tree[], ll n, ll s, ll e, ll tgIdx, ll val) {
   if (s == e) {
      tree[n] += val;
      return;
   }
   ll lch = n * 2, rch = lch + 1, m = (s + e) / 2;
   if (tgIdx <= m) update(tree, lch, s, m, tgIdx, val);
   else update(tree, rch, m + 1, e, tgIdx, val);
   tree[n] = tree[lch] + tree[rch];
}

ll query(ll tree[], ll n, ll s, ll e, ll fs, ll fe) {
   if (e < fs || fe < s) return 0;
   if (fs <= s && e <= fe) return tree[n];
   ll lch = n * 2, rch = lch + 1, m = (s + e) / 2;
   ll left = query(tree, lch, s, m, fs, fe);
   ll right = query(tree, rch, m + 1, e, fs, fe);
   return left + right;
}

void segclear() {
   for (ll i = 0; i < 8 * MAXN; i++)
      tree1[i] = tree3[i] = 0;
}

vector<ll> g[MAXN];
ll ans[MAXN];
ll totSP[MAXN]{};
ll cnts[MAXN]{};

void solve() {
   for (int i = 0; i < MAXN; i++)
      ans[i] = -1;
   Euler_tour(1, 0); // for setting in, out, par
   set_parent(); // for faster LCA(O(logN))
   for (int i = 0; i < Q; i++) { // set for PBS
      l[i] = -1;
      r[i] = M;
   }

   for (int i = 0; i < M; i++) {
      int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
      if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
      update(tree2, 1, 1, Euler_tour_idx, in[E], 1); // SP 추가
      update(tree2, 1, 1, Euler_tour_idx, out[E], -1);
   }

   for (int j = 0; j < Q; j++) {
      int tmp_lca = LCA(queries[j].s, queries[j].t);
      ll tmp = query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree2, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
      totSP[j] = tmp;
   }

   while (1) {
      for (int i = 0; i < MAXN; i++)
         g[i].clear();
      segclear();
      bool flag = 0;
      for (int i = 0; i < Q; i++) {
         if (l[i] + 1 == r[i]) continue;
         flag = 1; g[l[i] + r[i] >> 1].push_back(i);
      }
      if (!flag) break;

      for (int i = 0; i < M; i++) {
         ll S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
         if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
         update(tree1, 1, 1, Euler_tour_idx, in[E], VAL); // SP (은화 가중치) 추가
         update(tree1, 1, 1, Euler_tour_idx, out[E], -VAL);
         update(tree3, 1, 1, Euler_tour_idx, in[E], 1); // SP (단순 개수) 추가
         update(tree3, 1, 1, Euler_tour_idx, out[E], -1);
         for (auto j : g[i]) {
            ll tmp_lca = LCA(queries[j].s, queries[j].t);
            ll tmp = query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree1, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
            ll tmp3 = query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree3, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
            if (tmp <= queries[j].y) {
               ans[j] = max(ans[j], queries[j].x - totSP[j] + tmp3);
               l[j] = i;
            }
            else r[j] = i;
         }
      }
   }
}

void output() {
   for (int i = 0; i < Q; i++) {
      if (ans[i] == -1 && queries[i].x >= totSP[i])
         ans[i] = queries[i].x - totSP[i];
      cout << ans[i] << '\n';
   }
}

int main() {
   fastIO();
   input();
   solve();
   output();
   return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Euler_tour(int, int)':
currencies.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for (int i = 0; i < adj[n].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:153:37: warning: unused variable 'VAL' [-Wunused-variable]
  153 |       int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
      |                                     ^~~
currencies.cpp:172:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |          flag = 1; g[l[i] + r[i] >> 1].push_back(i);
      |                      ~~~~~^~~~~~

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