oj.uz

Submission #219756

# Submission time Handle Problem Language Result Execution time Memory
219756 2020-04-06T09:13:12 Z rama_pang Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 48856 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<vector<lint>> optimal; // optimal[v][k] = for subtree v, res[k + 1] - res[k] 
                              // where res[k] is the optimal way of picking k nodes in 
                              // subtree of v such that the edge cost away from v is maximum

void Solve(int R) {
  function<void(int, int)> dfs = [&](int n, int p) {
    optimal[n].emplace_back(0);
    for (const auto &i : adj[n]) if (i.v != p && !processed[i.v]) {
      dfs(i.v, n);
      optimal[i.v].front() += i.away;
      if (optimal[n].size() < optimal[i.v].size()) {
        swap(optimal[i.v], optimal[n]);
      }
      if (optimal[i.v].front() > optimal[n].front()) {
        swap(optimal[i.v].front(), optimal[n].front());
      }
      for (const auto &j : optimal[i.v]) {
        optimal[n].emplace_back(j);
      }
      optimal[i.v].clear();
      optimal[i.v].shrink_to_fit();
    }
  };

  for (const auto &i : adj[R]) if (!processed[i.v]) {
    dfs(i.v, R);
    optimal[i.v].front() += i.away;
  }

  vector<lint> all;
  for (const auto &i : adj[R]) if (!processed[i.v]) {
    all.insert(end(all), begin(optimal[i.v]), end(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].front() > mx.first) {
        mx.second = mx.first;
        mx.first = optimal[i.v].front();
      } else if (optimal[i.v].front() > mx.second) {
        mx.second = optimal[i.v].front();
      }
    }
    
    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);
        }
      }
    }
  }

  for (const auto &i : adj[R]) if (!processed[i.v]) {
    optimal[i.v].clear();
    optimal[i.v].shrink_to_fit();
  }
}

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:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < all.size(); i++) {
                     ~~^~~~~~~~~~~~
designated_cities.cpp:133: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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 1355 ms 34112 KB Output is correct
3 Execution timed out 2004 ms 46300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1424 ms 33624 KB Output is correct
3 Execution timed out 2027 ms 48856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 1355 ms 34112 KB Output is correct
3 Execution timed out 2004 ms 46300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 1355 ms 34112 KB Output is correct
14 Execution timed out 2004 ms 46300 KB Time limit exceeded
15 Halted 0 ms 0 KB -