Submission #1360251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360251		altern23	Designated Cities (JOI19_designated_cities)	C++20	23 / 100	2096 ms	41988 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 2e5;

vector <pair<ll, ll>> adj[MAXN+5];
ll M;

ll dist[MAXN+5], ans[MAXN+5], tmp[MAXN+5], P[MAXN+5];

vector <pair<ll, ll>> dp[MAXN+5];

void dfs(ll idx, ll par) {
      dp[idx].push_back({dist[idx], idx});
      for (auto [i, j] : adj[idx]) {
            if (i == par) M -= j;
            else {
                  dist[i] = dist[idx]+j;
                  P[i] = idx;
                  dfs(i, idx);
                  dp[idx].push_back({dp[i].back().first, dp[i].back().second});
            }
      }
      sort(dp[idx].begin(), dp[idx].end());
}

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N; cin >> N;

            for (int i = 0; i <= N; i++) {
                  ans[i] = 1e18;
                  tmp[i] = 1e18;
            }
            
            ll m = 0;

            for (int i = 2; i <= N; i++) {
                  ll u, v, a, b; cin >> u >> v >> a >> b;
                  m += a+b;
                  adj[u].push_back({v, a});
                  adj[v].push_back({u, b});

            }

            for (int root = 1; root <= N; root++) {
                  for (int i = 1; i <= N; i++) {
                        dp[i].clear();
                        dist[i] = P[i] = 0;
                  }

                  M = m;

                  dfs(root, -1);

                  priority_queue<pair<ll, ll>> pq;

                  vector <ll> vis(N+5);

                  pq.push(dp[root].back());
                  ll x = 1;
                  tmp[x] = M;
                  ans[x] = min(ans[x], tmp[x]);

                  while (!pq.empty()) {
                        auto [val, idx] = pq.top(); pq.pop();
                        tmp[x+1] = tmp[x]-val;
                        ans[x+1] = min(ans[x+1], tmp[x+1]);
                        x++;
                        while (idx) {
                              dp[idx].pop_back();
                              if (!dp[idx].empty()) {
                                    pq.push({dp[idx].back().first-dist[idx], dp[idx].back().second});
                              }
                              if (vis[idx]) break;
                              vis[idx] = 1;
                              idx = P[idx];
                        }
                  }
            }

            for (int i = 1; i <= N; i++) ans[i] = min(ans[i-1], ans[i]);

            ll Q; cin >> Q;
            for (int i = 1; i <= Q; i++) {
                  ll z; cin >> z;
                  cout << ans[z] << "\n";
            }
      }
}

/*

*/

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