oj.uz

Submission #520393

# Submission time Handle Problem Language Result Execution time Memory
520393 2022-01-29T18:35:27 Z Alex_tz307 Traffickers (RMI18_traffickers) C++17
100 / 100
 661 ms 60448 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e4 + 1;
const int MAXM = 6e4 + 1;
const int MAXD = 21;
int n, m, timer, tin[MAXN], tout[MAXN], tour[MAXM], depth[MAXM], first[MAXN], par[MAXN], lg2[MAXM], rmq[16][MAXM], nodes[MAXD], aux[MAXD], cnt[MAXD][MAXN][MAXD];
vector<int> g[MAXN];

void dfs(int u, int level) {
  tin[u] = ++timer;
  tour[++m] = u;
  depth[m] = level;
  first[u] = m;
  for (int v : g[u]) {
    if (v != par[u]) {
      par[v] = u;
      dfs(v, level + 1);
      tour[++m] = u;
      depth[m] = level;
    }
  }
  tout[u] = timer;
}

void compute_rmq() {
  for (int i = 2; i <= m; ++i) {
    lg2[i] = lg2[i >> 1] + 1;
  }
  for (int i = 1; i <= m; ++i) {
    rmq[0][i] = i;
  }
  for (int i = 1; (1 << i) < m; ++i) {
    for (int j = 1; j <= m - (1 << i); ++j) {
      int l = 1 << (i - 1);
      rmq[i][j] = rmq[i - 1][j];
      if (depth[rmq[i - 1][j + l]] < depth[rmq[i][j]]) {
        rmq[i][j] = rmq[i - 1][j + l];
      }
    }
  }
}

int find_lca(int u, int v) {
  int x = first[u], y = first[v];
  if (x > y) {
    swap(x, y);
  }
  int diff = y - x + 1;
  int l = lg2[diff];
  int sol = rmq[l][x];
  int shift = diff - (1 << l);
  if (depth[sol] > depth[rmq[l][x + shift]]) {
    sol = rmq[l][x + shift];
  }
  return tour[sol];
}

void update(int period, int u, int t, int val) {
  for (int i = u; i <= n; i += i & -i) {
    for (int j = t; j <= period; j += j & -j) {
      cnt[period][i][j] += val;
    }
  }
}

void update_path(int u, int v, int val) {
  int lca = find_lca(u, v), k = 0;
  while (u != lca) {
    nodes[k++] = u;
    u = par[u];
  }
  nodes[k++] = lca;
  int r = 0;
  while (v != lca) {
    aux[r++] = v;
    v = par[v];
  }
  for (int i = r - 1; i >= 0; --i) {
    nodes[k++] = aux[i];
  }
  for (int t = 0; t <= k - 1; ++t) {
    update(k, tin[nodes[t]], t + 1, val);
    update(k, tout[nodes[t]] + 1, t + 1, -val);
  }
}

int query_period(int period, int p, int q) {
  int ans = 0;
  for (int i = p; i >= 1; i -= i & -i) {
    for (int j = q; j >= 1; j -= j & -j) {
      ans += cnt[period][i][j];
    }
  }
  return ans;
}

int64_t query(int v, int t) {
  int64_t ans = 0;
  for (int period = 1; period <= MAXD - 1; ++period) {
    ans += (int64_t)query_period(period, tin[v], period) * (t / period) + query_period(period, tin[v], t % period + 1);
  }
  return ans;
}

int64_t query_pref(int u, int v, int t) {
  int lca = find_lca(u, v);
  return query(u, t) + query(v, t) - query(lca, t) - query(par[lca], t);
}

void testCase() {
  cin >> n;
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs(1, 0);
  compute_rmq();
  int k;
  cin >> k;
  for (int i = 1; i <= k; ++i) {
    int u, v;
    cin >> u >> v;
    update_path(u, v, 1);
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t <= 2) {
      update_path(u, v, 1 - ((t - 1) << 1));
    } else {
      int t1, t2;
      cin >> t1 >> t2;
      cout << query_pref(u, v, t2) - query_pref(u, v, t1 - 1) << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1224 KB Output is correct
2 Correct 4 ms 3012 KB Output is correct
3 Correct 4 ms 2948 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 19464 KB Output is correct
2 Correct 54 ms 17872 KB Output is correct
3 Correct 60 ms 18852 KB Output is correct
4 Correct 78 ms 19564 KB Output is correct
5 Correct 57 ms 19532 KB Output is correct
6 Correct 57 ms 19668 KB Output is correct
7 Correct 54 ms 19224 KB Output is correct
8 Correct 59 ms 19376 KB Output is correct
9 Correct 52 ms 19272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 59404 KB Output is correct
2 Correct 581 ms 60280 KB Output is correct
3 Correct 654 ms 59792 KB Output is correct
4 Correct 624 ms 58940 KB Output is correct
5 Correct 661 ms 58668 KB Output is correct
6 Correct 573 ms 60228 KB Output is correct
7 Correct 447 ms 60448 KB Output is correct
8 Correct 441 ms 60040 KB Output is correct