oj.uz

Submission #200574

# Submission time Handle Problem Language Result Execution time Memory
200574 2020-02-07T12:08:54 Z EntityIT Designated Cities (JOI19_designated_cities) C++14
33 / 100
 473 ms 42216 KB 
#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() ) return ;

    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
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 416 ms 28520 KB Output is correct
3 Correct 473 ms 42216 KB Output is correct
4 Correct 394 ms 26292 KB Output is correct
5 Correct 383 ms 28520 KB Output is correct
6 Correct 419 ms 30492 KB Output is correct
7 Correct 329 ms 29656 KB Output is correct
8 Correct 452 ms 41576 KB Output is correct
9 Correct 249 ms 33232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 405 ms 28648 KB Output is correct
3 Correct 438 ms 38760 KB Output is correct
4 Correct 386 ms 24168 KB Output is correct
5 Correct 384 ms 25196 KB Output is correct
6 Correct 401 ms 27624 KB Output is correct
7 Correct 262 ms 29136 KB Output is correct
8 Correct 437 ms 34280 KB Output is correct
9 Correct 247 ms 29644 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 416 ms 28520 KB Output is correct
3 Correct 473 ms 42216 KB Output is correct
4 Correct 394 ms 26292 KB Output is correct
5 Correct 383 ms 28520 KB Output is correct
6 Correct 419 ms 30492 KB Output is correct
7 Correct 329 ms 29656 KB Output is correct
8 Correct 452 ms 41576 KB Output is correct
9 Correct 249 ms 33232 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 405 ms 28648 KB Output is correct
12 Correct 438 ms 38760 KB Output is correct
13 Correct 386 ms 24168 KB Output is correct
14 Correct 384 ms 25196 KB Output is correct
15 Correct 401 ms 27624 KB Output is correct
16 Correct 262 ms 29136 KB Output is correct
17 Correct 437 ms 34280 KB Output is correct
18 Correct 247 ms 29644 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 421 ms 24908 KB Output is correct
21 Correct 442 ms 38760 KB Output is correct
22 Correct 394 ms 24168 KB Output is correct
23 Correct 389 ms 25064 KB Output is correct
24 Correct 386 ms 25192 KB Output is correct
25 Correct 405 ms 24936 KB Output is correct
26 Correct 381 ms 25064 KB Output is correct
27 Correct 386 ms 25088 KB Output is correct
28 Correct 411 ms 27488 KB Output is correct
29 Correct 390 ms 24808 KB Output is correct
30 Correct 375 ms 25064 KB Output is correct
31 Correct 321 ms 27608 KB Output is correct
32 Correct 436 ms 34792 KB Output is correct
33 Correct 258 ms 29660 KB Output is correct

Subtask #6
0 / 44.0

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