Submission #1162111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162111		fryingduc	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	462 ms	47036 KiB

designated_cities

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q;
vector<pair<int, int>> g[maxn];
int eu[maxn], ev[maxn], ec[maxn], ed[maxn];
int par[maxn], w[maxn];
long long tot;
long long res[maxn];
long long dep[maxn];
bool active[maxn];
int tin[maxn], tout[maxn], timer, et[maxn];

void pre_dfs(int u, int prev) {
  for (auto [v, id] : g[u]) {
    if (v == prev) continue;
    par[v] = u;
    dep[v] = dep[u] + (v == ev[id] ? ec[id] : ed[id]);
    pre_dfs(v, u);
  }
}

pair<long long, int> tree[maxn << 2];
long long lazy[maxn << 2];

void build(int ind = 1, int l = 1, int r = n) {
  if (l == r) {
    tree[ind] = make_pair(dep[et[l]], et[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(ind << 1, l, mid);
  build(ind << 1 | 1, mid + 1, r);
  tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
}

void down(int ind, int l, int r) {
  tree[ind].first += lazy[ind];
  if (l != r) {
    lazy[ind << 1] += lazy[ind];
    lazy[ind << 1 | 1] += lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, long long val, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] = val;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, val, ind << 1, l, mid);
  update(x, y, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
}

pair<long long, int> get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return make_pair(0, 0);
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return max(get(x, y, ind << 1, l, mid), get(x, y, ind << 1 | 1, mid + 1, r));
}

void dfs(int u, int prev) {
  tin[u] = ++timer;
  et[timer] = u;
  for (auto [v, id] : g[u]) {
    if (v == prev) continue;
    active[v] = 1;
    w[v] = (v == ev[id] ? ec[id] : ed[id]);
    dfs(v, u);
  }
  tout[u] = timer;
}

void dfs_one(int u, int prev, long long d = 0) {
  res[1] = min(res[1], d);
  for (auto [v, id] : g[u]) {
    if (v == prev) continue;
    dfs_one(v, u, d + (v == ev[id] ? ed[id] - ec[id] : ec[id] - ed[id]));
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v >> ec[i] >> ed[i];
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
    eu[i] = u, ev[i] = v;
  }
  pre_dfs(1, 0);
  int r1 = max_element(dep + 1, dep + n + 1) - dep;
  dep[r1] = par[r1] = 0;
  pre_dfs(r1, 0);
  int r2 = 0;
  for (int i = 1; i <= n; ++i) {
    if (i == r1) continue;
    if (r2 == 0 || dep[r2] < dep[i]) r2 = i;
  }
  long long tot = 0;
  for (int i = 1; i < n; ++i) {
    tot += (par[ev[i]] == eu[i] ? ec[i] : ed[i]);
  }
  res[1] = 1e18;
  dfs_one(r1, 0, tot);
  dfs(r1, 0);
  build();
  for (int i = 2; i <= n; ++i) {
    auto t = get(1, n);
    tot -= t.first;
//    debug(t.first);
    res[i] = tot;
    int cur = t.second;
    while (active[cur]) {
      update(tin[cur], tout[cur], -w[cur]);
      active[cur] = 0;
      cur = par[cur];
    }
  }  
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int x; cin >> x;
    cout << res[x] << '\n';
  }
}

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

  solve();

  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44