Submission #200575

#	Time	Username	Problem	Language	Result	Execution time	Memory
200575		EntityIT	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	487 ms	40020 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n;
vector<vector<pair<int, int> > > gr;
vector<int> eCost;
LL sum;

vector<LL> ans;

vector<LL> inCost;
LL getUp(int u, int pr) {
  LL ret = 0;
  for (auto e : gr[u]) if (e.first != pr) ret += getUp(e.first, u) + eCost[e.second ^ 1];
  return ret;
}
void calInCost(int u, int pr) {
  for (auto e : gr[u]) {
    int v = e.first, id = e.second;
    if (v == pr) continue ;
    inCost[v] = inCost[u] - eCost[id ^ 1] + eCost[id];
    calInCost(v, u);
  }
}
void calAns1() {
  inCost.assign(n, 0);
  inCost[0] = getUp(0, -1);
  calInCost(0, -1);
  ans = { 0, *max_element(all(inCost) ) };
}

pair<LL, int> dfs(int u, int pr, tuple<LL, int, int> &mx) {
  pair<LL, int> prv = { inCost[u], u };

  for (auto e : gr[u]) {
    int v = e.first, id = e.second;
    if (v == pr) continue ;

    auto cur = dfs(v, u, mx); cur.first += eCost[id] + eCost[id ^ 1];
    asMx(mx, { prv.first + cur.first, prv.second, cur.second } );
    asMx(prv, cur);
  }
  return prv;
}
int getRt() {
  tuple<LL, int, int> mx{ 0, 0, 0 };
  dfs(0, -1, mx);
  return get<1>(mx);
}

int rt;
vector<pair<LL, int> > mxDep;
vector<int> par;
void calMxDep(int u, int pr, int upCost = 0) {
  par[u] = pr;
  mxDep[u] = { 0, u };
  for (auto e : gr[u]) {
    int v = e.first, id = e.second;
    if (v == pr) continue ;
    calMxDep(v, u, eCost[id]);
    asMx(mxDep[u], mxDep[v]);
  }
  mxDep[u].first += upCost;
}
void prep() {
  rt = getRt();

  mxDep.assign(n, { -1, -1 } );
  par.assign(n, -1);
  calMxDep(rt, -1);
}
void calAns() {
  calAns1();

  prep();
  LL curAns = inCost[rt];
  priority_queue<pair<LL, int> > pq; pq.emplace(mxDep[rt]);
  vector<bool> done(n, false); done[rt] = true;
  for (int i = 2; i <= n; ++i) {
    if (pq.empty() ) {
      ans.emplace_back(curAns);
      continue ;
    }

    LL bonus = pq.top().first; int u = pq.top().second; pq.pop();
    ans.emplace_back(curAns += bonus);

    vector<int> path;
    for (; !done[u]; u = par[u]) {
      path.emplace_back(u);
      done[u] = true;
    }
    reverse(all(path) );

    for (int j = 0; j + 1 < sz(path); ++j) {
      u = path[j]; int v = path[j + 1];

      for (auto e : gr[u]) {
        int w = e.first;
        if (w == par[u] || w == v) continue ;
        pq.emplace(mxDep[w]);
      }
    }
  }
}

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n;
  gr.assign(n, {} );
  for (int i = 0; i < n - 1; ++i) {
    int u, v, c, d; cin >> u >> v >> c >> d; --u; --v;
    gr[u].emplace_back(v, sz(eCost) ); eCost.emplace_back(c);
    gr[v].emplace_back(u, sz(eCost) ); eCost.emplace_back(d);
    sum += c + d;
  }

  calAns();

  int q; cin >> q;
  while (q--) {
    int e; cin >> e;
    cout << sum - ans[e] << '\n';
  }

  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