oj.uz

Submission #219757

# Submission time Handle Problem Language Result Execution time Memory
219757 2020-04-06T09:23:08 Z rama_pang Designated Cities (JOI19_designated_cities) C++14
100 / 100
 1468 ms 41564 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

struct edge_t {
  int v;
  int away;
  int come;
  edge_t() {}
  edge_t(int v, int a, int c) : v(v), away(a), come(c) {}
};

int N;
vector<vector<edge_t>> adj;

vector<lint> Answer;
vector<lint> BaseCost; // BaseCost[i] = sum of all edges going to i (root at i), so we do not need to consider them afterwards
vector<bool> processed; // processed as R, done via centroid decomposition

void GenerateBaseCost() {
  vector<lint> dp(N);
  function<void(int, int)> dfs = [&](int n, int p) {
    for (const auto &i : adj[n]) if (i.v != p) {
      dfs(i.v, n);
      dp[n] += dp[i.v] + i.come;
    }
  };

  function<void(int, int)> reroot = [&](int n, int p) {
    BaseCost[n] = dp[n];
    for (const auto &i : adj[n]) if (i.v != p) {
      dp[n] -= dp[i.v] + i.come;
      dp[i.v] += dp[n] + i.away;
      reroot(i.v, n);
      dp[i.v] -= dp[n] + i.away;
      dp[n] += dp[i.v] + i.come;
    }
  };

  dfs(0, -1);
  reroot(0, -1);

}

vector<int> sz; // subtree size

int Centroid(int n) {
  function<void(int, int)> dfs = [&](int n, int p) {
    sz[n] = 1;
    for (const auto &i : adj[n]) if (i.v != p && !processed[i.v]) {
      dfs(i.v, n);
      sz[n] += sz[i.v];
    }
  };

  dfs(n, -1);
  int cur = n, p = -1;
  while (true) {
    pair<int, int> mx = {-1, -1};
    for (const auto &i : adj[cur]) if (i.v != p && !processed[i.v]) {
      mx = max(mx, {sz[i.v], i.v});
    }
    if (mx.first * 2 <= sz[n]) {
      return cur;
    }
    p = cur;
    cur = mx.second;
  }
}

vector<lint> optimal; // maximum weighted depth

void Solve(int R) {
  function<lint(int, int, vector<lint>&)> dfs = [&](int n, int p, vector<lint> &v) {
    lint cur = 0;
    for (const auto &i : adj[n]) if (i.v != p && !processed[i.v]) {
      lint nxt = dfs(i.v, n, v) + i.away;
      if (cur < nxt) swap(cur, nxt);
      if (nxt > 0) v.emplace_back(nxt);
    }
    return cur;
  };

  vector<lint> all;
  for (const auto &i : adj[R]) if (!processed[i.v]) {
    optimal[i.v] = dfs(i.v, R, all) + i.away;
    all.emplace_back(optimal[i.v]);
  }
  sort(begin(all), end(all), greater<lint>());

  { // Case #1: R is chosen
    lint sum = BaseCost[R]; 
    int cnt = 1;
    Answer[cnt] = max(Answer[cnt], sum);

    for (int i = 0; i < all.size(); i++) {
      sum += all[i], cnt++;
      Answer[cnt] = max(Answer[cnt], sum);
    }
  }

  { // Case #2: R is not chosen, two different subtrees
    pair<lint, lint> mx = {-1, -1};
    for (const auto &i : adj[R]) if (!processed[i.v]) {
      if (optimal[i.v] > mx.first) {
        mx.second = mx.first;
        mx.first = optimal[i.v];
      } else if (optimal[i.v] > mx.second) {
        mx.second = optimal[i.v];
      }
    }
    
    if (mx.first != -1 && mx.second != -1) {
     lint sum = BaseCost[R] + mx.first + mx.second; 
      int cnt = 2;
      Answer[cnt] = max(Answer[cnt], sum);

      for (int i = 0; i < all.size(); i++) {
        if (all[i] == mx.first) {
          mx.first = -1;
        } else if (all[i] == mx.second) {
          mx.second = -1;
        } else {
          sum += all[i], cnt++;
          Answer[cnt] = max(Answer[cnt], sum);
        }
      }
    }
  }
}

void CentroidDecomposition() {
  queue<int> q;
  q.emplace(0);
  while (!q.empty()) {
    int R = Centroid(q.front());
    q.pop();
    Solve(R);
    processed[R] = true;
    for (const auto &i : adj[R]) if (!processed[i.v]) {
      q.emplace(i.v);
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;

  sz.resize(N);  
  adj.resize(N);
  optimal.resize(N);
  BaseCost.resize(N);
  Answer.resize(N + 1);
  processed.resize(N, false);

  lint sum_all_costs = 0;
  for (int i = 0; i < N - 1; i++) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    A--, B--;
    adj[A].emplace_back(B, C, D);
    adj[B].emplace_back(A, D, C);
    sum_all_costs += C + D;
  }

  GenerateBaseCost();
  CentroidDecomposition();

  for (int i = 1; i <= N; i++) {
    Answer[i] = max(Answer[i], Answer[i - 1]);
  }
  for (int i = 1; i <= N; i++) {
    Answer[i] = sum_all_costs - Answer[i];
  }

  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int E;
    cin >> E;
    cout << Answer[E] << "\n";
  }

  return 0;
}

Compilation message

designated_cities.cpp: In function 'void Solve(int)':
designated_cities.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < all.size(); i++) {
                     ~~^~~~~~~~~~~~
designated_cities.cpp:118:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < all.size(); i++) {
                       ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 971 ms 20524 KB Output is correct
3 Correct 1452 ms 32420 KB Output is correct
4 Correct 929 ms 25536 KB Output is correct
5 Correct 438 ms 26896 KB Output is correct
6 Correct 1041 ms 29104 KB Output is correct
7 Correct 347 ms 27156 KB Output is correct
8 Correct 1320 ms 39432 KB Output is correct
9 Correct 242 ms 29316 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 893 ms 20568 KB Output is correct
3 Correct 1313 ms 34944 KB Output is correct
4 Correct 879 ms 25560 KB Output is correct
5 Correct 458 ms 27024 KB Output is correct
6 Correct 1068 ms 29356 KB Output is correct
7 Correct 251 ms 28812 KB Output is correct
8 Correct 1243 ms 35416 KB Output is correct
9 Correct 253 ms 28936 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 9 ms 672 KB Output is correct
14 Correct 7 ms 640 KB Output is correct
15 Correct 7 ms 512 KB Output is correct
16 Correct 9 ms 512 KB Output is correct
17 Correct 9 ms 568 KB Output is correct
18 Correct 9 ms 512 KB Output is correct
19 Correct 9 ms 512 KB Output is correct
20 Correct 7 ms 512 KB Output is correct
21 Correct 8 ms 512 KB Output is correct
22 Correct 7 ms 512 KB Output is correct
23 Correct 8 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 8 ms 640 KB Output is correct
26 Correct 7 ms 640 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 971 ms 20524 KB Output is correct
3 Correct 1452 ms 32420 KB Output is correct
4 Correct 929 ms 25536 KB Output is correct
5 Correct 438 ms 26896 KB Output is correct
6 Correct 1041 ms 29104 KB Output is correct
7 Correct 347 ms 27156 KB Output is correct
8 Correct 1320 ms 39432 KB Output is correct
9 Correct 242 ms 29316 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 893 ms 20568 KB Output is correct
12 Correct 1313 ms 34944 KB Output is correct
13 Correct 879 ms 25560 KB Output is correct
14 Correct 458 ms 27024 KB Output is correct
15 Correct 1068 ms 29356 KB Output is correct
16 Correct 251 ms 28812 KB Output is correct
17 Correct 1243 ms 35416 KB Output is correct
18 Correct 253 ms 28936 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 898 ms 26972 KB Output is correct
21 Correct 1284 ms 41564 KB Output is correct
22 Correct 877 ms 25560 KB Output is correct
23 Correct 896 ms 26980 KB Output is correct
24 Correct 889 ms 25948 KB Output is correct
25 Correct 884 ms 26968 KB Output is correct
26 Correct 879 ms 25968 KB Output is correct
27 Correct 445 ms 26904 KB Output is correct
28 Correct 1035 ms 29016 KB Output is correct
29 Correct 870 ms 26944 KB Output is correct
30 Correct 748 ms 26256 KB Output is correct
31 Correct 297 ms 28300 KB Output is correct
32 Correct 1224 ms 35932 KB Output is correct
33 Correct 237 ms 29468 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 971 ms 20524 KB Output is correct
14 Correct 1452 ms 32420 KB Output is correct
15 Correct 929 ms 25536 KB Output is correct
16 Correct 438 ms 26896 KB Output is correct
17 Correct 1041 ms 29104 KB Output is correct
18 Correct 347 ms 27156 KB Output is correct
19 Correct 1320 ms 39432 KB Output is correct
20 Correct 242 ms 29316 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 893 ms 20568 KB Output is correct
23 Correct 1313 ms 34944 KB Output is correct
24 Correct 879 ms 25560 KB Output is correct
25 Correct 458 ms 27024 KB Output is correct
26 Correct 1068 ms 29356 KB Output is correct
27 Correct 251 ms 28812 KB Output is correct
28 Correct 1243 ms 35416 KB Output is correct
29 Correct 253 ms 28936 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 9 ms 672 KB Output is correct
32 Correct 7 ms 640 KB Output is correct
33 Correct 7 ms 512 KB Output is correct
34 Correct 9 ms 512 KB Output is correct
35 Correct 9 ms 568 KB Output is correct
36 Correct 9 ms 512 KB Output is correct
37 Correct 9 ms 512 KB Output is correct
38 Correct 7 ms 512 KB Output is correct
39 Correct 8 ms 512 KB Output is correct
40 Correct 7 ms 512 KB Output is correct
41 Correct 8 ms 640 KB Output is correct
42 Correct 6 ms 640 KB Output is correct
43 Correct 8 ms 640 KB Output is correct
44 Correct 7 ms 640 KB Output is correct
45 Correct 4 ms 384 KB Output is correct
46 Correct 898 ms 26972 KB Output is correct
47 Correct 1284 ms 41564 KB Output is correct
48 Correct 877 ms 25560 KB Output is correct
49 Correct 896 ms 26980 KB Output is correct
50 Correct 889 ms 25948 KB Output is correct
51 Correct 884 ms 26968 KB Output is correct
52 Correct 879 ms 25968 KB Output is correct
53 Correct 445 ms 26904 KB Output is correct
54 Correct 1035 ms 29016 KB Output is correct
55 Correct 870 ms 26944 KB Output is correct
56 Correct 748 ms 26256 KB Output is correct
57 Correct 297 ms 28300 KB Output is correct
58 Correct 1224 ms 35932 KB Output is correct
59 Correct 237 ms 29468 KB Output is correct
60 Correct 5 ms 384 KB Output is correct
61 Correct 957 ms 29580 KB Output is correct
62 Correct 1468 ms 40584 KB Output is correct
63 Correct 886 ms 28312 KB Output is correct
64 Correct 884 ms 29788 KB Output is correct
65 Correct 880 ms 28252 KB Output is correct
66 Correct 914 ms 29528 KB Output is correct
67 Correct 929 ms 28224 KB Output is correct
68 Correct 538 ms 29588 KB Output is correct
69 Correct 1150 ms 31300 KB Output is correct
70 Correct 941 ms 29144 KB Output is correct
71 Correct 772 ms 29072 KB Output is correct
72 Correct 366 ms 30468 KB Output is correct
73 Correct 1258 ms 36860 KB Output is correct
74 Correct 263 ms 31984 KB Output is correct