oj.uz

Submission #682521

# Submission time Handle Problem Language Result Execution time Memory
682521 2023-01-16T12:27:58 Z peijar Designated Cities (JOI19_designated_cities) C++17
7 / 100
 1163 ms 92216 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e6;

int iDeb[MAXN], iFin[MAXN], lazy[MAXN];
pair<int, int> seg[MAXN];

void pull(int node) { seg[node] = max(seg[2 * node], seg[2 * node + 1]); }

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  lazy[node] = 0;
  if (l == r) {
    seg[node] = pair(0, l);
    return;
  }

  int m = (l + r) / 2;
  build(2 * node, l, m);
  build(2 * node + 1, m + 1, r);
}

void push(int node) {
  if (!lazy[node])
    return;
  int x = lazy[node];
  lazy[node] = 0;

  seg[node].first += x;
  if (iDeb[node] < iFin[node]) {
    lazy[2 * node] += x, lazy[2 * node + 1] += x;
  }
}

void rangeAdd(int node, int l, int r, int x) {
  push(node);
  if (iDeb[node] > r or iFin[node] < l)
    return;
  if (l <= iDeb[node] and iFin[node] <= r) {
    lazy[node] = x;
    push(node);
    return;
  }
  rangeAdd(2 * node, l, r, x);
  rangeAdd(2 * node + 1, l, r, x);
  pull(node);
}

const int INF = 1e12;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet;
  cin >> nbSommet;
  int tot = 0;

  vector<vector<tuple<int, int, int>>> adj(nbSommet);
  for (int i = 1; i < nbSommet; ++i) {
    int u, v, C, D;
    cin >> u >> v >> C >> D;
    --u, --v;
    adj[u].emplace_back(v, C, D);
    adj[v].emplace_back(u, D, C);
    tot += C + D;
  }

  vector<int> par(nbSommet), costDown(nbSommet), costUp(nbSommet);
  vector<int> tin(nbSommet), tout(nbSommet);
  vector<int> order;
  int Time = 0;

  auto Dfs = [&](auto dfs, int u, int p) -> void {
    par[u] = p;
    tin[u] = Time++;
    order.push_back(u);
    for (auto [v, down, up] : adj[u])
      if (v != p) {
        costDown[v] = up;
        costUp[v] = down;
        dfs(dfs, v, u);
      }
    tout[u] = Time;
  };

  Dfs(Dfs, 0, 0);

  dbg(tin, tout);
  dbg(order);

  build(1, 0, Time - 1);

  for (int u = 1; u < nbSommet; ++u) {
    rangeAdd(1, 0, Time - 1, costDown[u]);
    rangeAdd(1, tin[u], tout[u] - 1, costUp[u] - costDown[u]);
  }
  vector<bool> cleared(nbSommet);

  auto Clear = [&](auto clear, int u) {
    if (!u or cleared[u])
      return;
    cleared[u] = true;
    rangeAdd(1, tin[u], tout[u] - 1, -costUp[u]);
    clear(clear, par[u]);
  };

  set<pair<int, int>> byTin, byTout;
  for (int u = 1; u < nbSommet; ++u)
    byTin.emplace(tin[u], u), byTout.emplace(tout[u], u);

  vector<bool> downRemoved(nbSommet);
  vector<int> sol(nbSommet + 1);
  sol[1] = seg[1].first;
  for (int u = 0; u < nbSommet; ++u)
    if (adj[u].size() > 1)
      rangeAdd(1, tin[u], tin[u], -INF);
  int curSol = 0;
  for (int i = 1; i <= nbSommet; ++i) {
    auto [add, u] = seg[1];
    u = order[u];
    curSol += add;
    dbg(u + 1, add);
    if (i > 1)
      sol[i] = curSol;

    Clear(Clear, u);

    auto it = byTin.begin();
    while ((it = byTin.lower_bound({tin[u] + 1, 0LL})) != byTin.end()) {
      auto [t, v] = *it;
      byTin.erase(it);
      if (!downRemoved[v]) {
        rangeAdd(1, 0, Time - 1, -costDown[v]);
        rangeAdd(1, tin[v], tout[v] - 1, costDown[v]);
        downRemoved[v] = true;
      }
    }
    auto it2 = byTout.begin();
    while ((it2 = byTout.lower_bound({tin[u] + 1, 0LL})) != byTout.begin()) {
      --it2;
      auto [t, v] = *it2;
      byTout.erase(it2);
      if (!downRemoved[v]) {
        rangeAdd(1, 0, Time - 1, -costDown[v]);
        rangeAdd(1, tin[v], tout[v] - 1, costDown[v]);
        downRemoved[v] = true;
      }
    }
  }

  int Q;
  cin >> Q;
  while (Q--) {
    int E;
    cin >> E;
    cout << tot - sol[E] << '\n';
  }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 948 ms 81124 KB Output is correct
3 Correct 979 ms 91760 KB Output is correct
4 Correct 831 ms 79828 KB Output is correct
5 Correct 933 ms 80836 KB Output is correct
6 Correct 1016 ms 82804 KB Output is correct
7 Correct 889 ms 80028 KB Output is correct
8 Correct 1163 ms 92216 KB Output is correct
9 Correct 751 ms 79016 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 877 ms 81216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 948 ms 81124 KB Output is correct
3 Correct 979 ms 91760 KB Output is correct
4 Correct 831 ms 79828 KB Output is correct
5 Correct 933 ms 80836 KB Output is correct
6 Correct 1016 ms 82804 KB Output is correct
7 Correct 889 ms 80028 KB Output is correct
8 Correct 1163 ms 92216 KB Output is correct
9 Correct 751 ms 79016 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 877 ms 81216 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -