Submission #918325

#	Time	Username	Problem	Language	Result	Execution time	Memory
918325		406	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	312 ms	62488 KiB

designated_cities

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;

vector<ar> adj[N];
int dp, mx[N], up[N], ans[N], n, q;

void dfs_dp(int v, int p) {
        for (auto [u, w]: adj[v]) {
                dp += (u == p ? w : 0);
        }
        for (auto [u, w]: adj[v]) if (u != p) {
                mx[u] = mx[v] + w;
                dfs_dp(u, v);
        }
}

void dfs_up(int v, int p) {
        for (auto [u, w]: adj[v]) up[v] -= (u == p ? w : 0);

        for (auto [u, w]: adj[v]) if (u != p) {
                up[u] = up[v] + w;
                dfs_up(u, v);
        }
}

vector<int> V;
int dfs(int v, int p) {
        if (adj[v].size() == 1 && v != p) return 0;
        vector<int> ch;
        for (auto [u, w]: adj[v]) if (u != p) {
                int x = dfs(u, v);
                ch.push_back(x + w);
        }
        sort(ch.begin(), ch.end());
        int u = ch.back();
        ch.pop_back();
        V.insert(V.end(), ch.begin(), ch.end());
        return u;
}


signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        int sum = 0;
        cin >> n;
        FOR(i, 1, n) {
                int u, v, c, d;
                cin >> u >> v >> c >> d;
                --u, --v;
                adj[u].push_back({v, c});
                adj[v].push_back({u, d});
                sum += c + d;
        }

        dfs_dp(0, 0);

        up[0] = dp;
        dfs_up(0, 0);
        int rt = max_element(mx, mx + n) - mx;
        ans[1] = *max_element(up, up + n);

        V.push_back(dfs(rt, rt));
        sort(V.rbegin(), V.rend());
        int kbig = 0;
        FOR(i, 2, n + 1) {
                kbig += (i - 2 < V.size() ? V[i - 2] : 0);
                ans[i] = up[rt] + kbig;
        }
                        

        cin >> q;
        FOR(i, 0, q) {
                int x;
                cin >> x;
                cout << sum - ans[x] << '\n';
        }
        return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:74:32: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 kbig += (i - 2 < V.size() ? V[i - 2] : 0);
      |                          ~~~~~~^~~~~~~~~~

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