Submission #1195951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195951		abczz	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	258 ms	47176 KiB

designated_cities

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

ll n, q, a, b, c, d, tot, f, t, id;
ll opt[200000], F[200000];
vector <ll> V[200000];
vector <array<ll, 3>> adj[200000];

ll dfs(ll u, ll p, ll w, ll s) {
  ll mx = -1e18, mx2 = -1e18;
  for (auto [v, x, y] : adj[u]) {
    if (v == p) continue;
    tot += x;
    ll tmp = dfs(v, u, w+y, s+y-x);
    if (mx < tmp) mx2 = mx, mx = tmp;
    else if (mx2 < tmp) mx2 = tmp;
  }
  t = min(t, s);
  if (f > w-mx-mx2) {
    f = w-mx-mx2;
    id = u;
  }
  return mx;
}

void solve(ll u, ll p) {
  opt[u] = 0;
  ll sz = -1, id = -1, id2 = -1;
  for (auto [v, x, y] : adj[u]) {
    if (v == p) continue;
    solve(v, u);
    opt[v] += x;
    if ((ll)V[v].size() > sz) sz = (ll)V[v].size(), id = v;
    if (opt[u] < opt[v]) {
      opt[u] = opt[v];
      id2 = v;
    }
  }
  if (id != -1) swap(V[u], V[id]);
  for (auto [v, x, y] : adj[u]) {
    if (v == p) continue;
    if (v != id) {
      for (auto z : V[v]) V[u].push_back(z);
    }
    if (v != id2) V[u].push_back(opt[v]);
  }
}

int main() {
  f = t = 1e18;
  cin >> n;
  for (int i=0; i<n; ++i) V[i].clear(), opt[i] = -1e18;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b >> c >> d;
    --a, --b;
    adj[a].push_back({b, c, d});
    adj[b].push_back({a, d, c});
  }
  dfs(0, -1, 0, 0);
  solve(id, -1);
  sort(V[id].begin(), V[id].end());
  F[0] = tot - opt[id];
  for (int i=1; i<n; ++i) {
    if (!V[id].empty()) {
      F[i] = F[i-1] - (ll)V[id].back();
      V[id].pop_back();
    }
    else F[i] = F[i-1];
  }
  F[0] = tot+t;
  cin >> q;
  while (q--) {
    cin >> a;
    --a;
    cout << F[a] << '\n';
  }
}

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