제출 #623132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623132		MilosMilutinovic	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	2059 ms	59600 KiB

designated_cities

/**
 *    author:  wxhtzdy
 *    created: 05.08.2022 10:18:20
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<array<int, 3>>> g(n);
  long long total = 0;
  for (int i = 0; i < n - 1; i++) {
    int x, y, w0, w1;
    cin >> x >> y >> w0 >> w1;
    --x; --y;
    g[x].push_back({y, w1, w0});
    g[y].push_back({x, w0, w1});
    total += w0;
    total += w1;
  }                       
  vector<long long> dp(n);
  vector<int> que(1, 0); 
  vector<bool> vis(n);
  vis[0] = true; 
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& p : g[i]) {
      int j = p[0];
      if (!vis[j]) {
        dp[0] += p[1];
        que.push_back(j);
        vis[j] = true;
      }
    }
  }
  function<void(int, int)> Dp = [&](int v, int pr) {
    for (auto& p : g[v]) {
      int u = p[0];
      if (u != pr) {
        dp[u] = dp[v] - p[1] + p[2];
        Dp(u, v);
      }
    }
  };
  Dp(0, 0);
  vector<long long> ans(n + 1);
  vector<int> sz(n);
  vector<bool> was(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    sz[v] = 1;
    for (auto& p : g[v]) {
      int u = p[0];
      if (!was[u] && u != pr) {
        Dfs(u, v);
        sz[v] += sz[u];
      }
    }
  };
  function<int(int, int, int)> Find = [&](int v, int pr, int n) {
    for (auto& p : g[v]) {
      int u = p[0];
      if (!was[u] && u != pr && sz[u] * 2 >= n) {
        return Find(u, v, n);
      }
    }
    return v;
  };                 
  vector<vector<pair<int, int>>> ch(n);
  vector<int> t;
  vector<int> nxt(n);
  function<void(int, int)> Go0 = [&](int v, int pr) {
    bool has = false;
    for (auto& p : g[v]) {
      int u = p[0];
      int w = p[1];
      if (!was[u] && u != pr) {
        Go0(u, v);         
        ch[v].push_back({p[2], u});
        has = true;
      }
    }
    if (has) {
      t.push_back(v);
    }
  };
  function<void(int)> Solve = [&](int v) {
    Dfs(v, v);
    v = Find(v, v, sz[v]);
    was[v] = true;
    long long cost = dp[v];
    Go0(v, v);
    set<pair<int, int>> edges;
    for (int i : t) {
      sort(ch[i].rbegin(), ch[i].rend());
      if (!ch[i].empty()) {
        edges.emplace(ch[i][0]);
        nxt[i] = 1;
      }
    }        
    for (int i = 1; i <= n; i++) {
      ans[i] = max(ans[i], cost);
      if (edges.empty()) {
        break;
      } else {
        auto it = prev(edges.end());
        cost += it->first;
        int u = it->second;
        edges.erase(it);  
        if (nxt[u] < (int) ch[u].size()) {
          edges.emplace(ch[u][nxt[u]]);
          nxt[u] += 1;
        }
      }
    }           
    for (int i : t) {
      ch[i].clear();
      nxt[i] = 0;
    }
    t.clear();
    for (auto& p : g[v]) {
      int u = p[0];
      if (!was[u]) {
        Solve(u);
      }
    }
  };
  Solve(0);
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    cout << total - ans[x] << '\n'; 
  }                                     
  return 0;
}

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

designated_cities.cpp: In lambda function:
designated_cities.cpp:79:11: warning: unused variable 'w' [-Wunused-variable]
   79 |       int w = p[1];
      |           ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44