Submission #897381

#	Time	Username	Problem	Language	Result	Execution time	Memory
897381		NeroZein	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	2036 ms	44216 KiB

designated_cities

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;

int n;
int cnt;
int euler[N];
bool active[N];
long long f[N];
long long ans[N];
int in[N], out[N];
long long dist[N];
pair<int, int> pr[N];
long long seg[N * 2];
long long lazy[N * 2];
vector<pair<int, int>> g[N];
pair<long long, long long> dp[N];

void dfs1(int v, int p) {
  long long mx = 0, mx2 = 0;
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    dist[1] += w;
    dfs1(u, v); 
    mx2 = max(mx2, dp[u].first + w); 
    if (mx2 > mx) swap(mx, mx2);
  }
  dp[v] = make_pair(mx, mx2);
}

void dfs2(int v, int p, long long up) {
  auto [mx, mx2] = dp[v];
  for (auto [u, w] : g[v]) {
    if (u == p) {
      dist[v] += w;
      up += w; 
    }
  }
  f[v] = max(mx, up);
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    dist[u] = dist[v] - w; 
    long long nup = (mx == dp[u].first + w ? mx2 : mx);
    nup = max(up, nup);
    dfs2(u, v, nup);
  }
}

void push(int nd, int l, int r) {
  if (!lazy[nd]) return;
  seg[nd] += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd];    
  }
  lazy[nd] = 0; 
}

void upd(int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r);
  if (l >= s && r <= e) {
    lazy[nd] = v; 
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    push(rs, mid + 1, r);
    upd(nd + 1, l, mid, s, e, v); 
  } else {
    if (mid < s) {
      push(nd + 1, l, mid);
      upd(rs, mid + 1, r, s, e, v); 
    } else {
      upd(nd + 1, l, mid, s, e, v);
      upd(rs, mid + 1, r, s, e, v);       
    }
  }
  seg[nd] = max(seg[nd + 1], seg[rs]); 
}

int get(int nd, int l, int r) {
  push(nd, l, r); 
  if (l == r) {
    return euler[l]; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  push(nd + 1, l, mid);
  push(rs, mid + 1, r); 
  if (seg[nd + 1] > seg[rs]) {
    return get(nd + 1, l, mid);
  }
  return get(rs, mid + 1, r); 
}

bool dfs3(int v, int p, int o) {
  euler[cnt] = v; 
  in[v] = cnt++;
  bool ret = o == v;
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    pr[u] = make_pair(v, w);
    bool ru = dfs3(u, v, o);
    if (!ru) {
      upd(0, 0, n - 1, in[u], out[u], w);
    } else {
      ret = true;
    }
  }
  out[v] = cnt - 1;
  active[v] = ret;
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    g[u].emplace_back(v, c);
    g[v].emplace_back(u, d); 
  }
  dfs1(1, 0);
  dfs2(1, 0, 0);
  ans[1] = *min_element(dist + 1, dist + 1 + n);
  ans[2] = LLONG_MAX;
  dist[0] = LLONG_MAX;
  int r = 0, o = 0; 
  for (int i = 1; i <= n; ++i) {
    if (dist[i] - f[i] < dist[r] - f[r]) {
      r = i;
    } else if (dist[i] - f[i] == dist[r] - f[r]) {
      o = i;
    }
  }
  ans[2] = dist[r] - f[r];
  dfs3(r, r, o);
  for (int i = 3; i <= n; ++i) {
    if (!seg[0]) break;
    ans[i] = ans[i - 1] - seg[0];
    int v = get(0, 0, n - 1);
    assert(v); 
    while (!active[v]) {
      auto [pv, pw] = pr[v];
      upd(0, 0, n - 1, in[v], out[v], -pw);
      v = pv; 
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int e;
    cin >> e;
    cout << ans[e] << '\n'; 
  }
  return 0;
}

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