제출 #219756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219756		rama_pang	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2027 ms	48856 KiB

designated_cities

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44