Submission #1211584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211584		JooDdae	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	287 ms	54176 KiB

designated_cities

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

int n, m, a[200200], b[200200], c[200200], d[200200];
ll ans[200200], dp[200200];
array<ll, 2> dp1[200200];
array<ll, 3> dp2[200200];
vector<int> v[200200];

void dfs(int u, int p) {
    for(auto i : v[u]) {
        int x = a[i] ^ b[i] ^ u;
        if(x == p) continue;
        dfs(x, u);
        dp[u] += dp[x] + (u == a[i] ? d[i] : c[i]);
    }

    dp1[u] = {dp[u], u}, dp2[u] = {0, u, u};

    for(auto i : v[u]) {
        int x = a[i] ^ b[i] ^ u;
        if(x == p) continue;

        int y = u == a[i] ? c[i] : d[i];
        int z = c[i] ^ d[i] ^ y;

        auto C = dp[u]-dp[x]-z;

        dp2[u] = max(dp2[u], array<ll, 3>({dp1[u][0]-dp[x]+dp1[x][0]+y, dp1[u][1], dp1[x][1]}));
        dp2[u] = max(dp2[u], array<ll, 3>({dp2[x][0]+y + C, dp2[x][1], dp2[x][2]}));
        
        dp1[u] = max(dp1[u], array<ll, 2>({dp1[x][0]+y+z + C, dp1[x][1]}));
    }
}

priority_queue<ll> pq;

ll dfs2(int u, int p) {
    if(u == dp2[1][2]) return 1e18;

    ll re = 0;
    for(auto i : v[u]) {
        int x = a[i] ^ b[i] ^ u;
        if(x == p) continue;
        ll K = dfs2(x, u) + (u == a[i] ? c[i] : d[i]);
        pq.push(min(re, K)), re = max(re, K);
    }
    return re;
}

void dfs3(int u, int p, ll S) {
    ans[1] = max(ans[1], S);
    for(auto i : v[u]) {
        int x = a[i] ^ b[i] ^ u;
        if(x == p) continue;
        dfs3(x, u, S + (u == a[i] ? c[i]-d[i] : d[i]-c[i]));
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<n;i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        v[a[i]].push_back(i), v[b[i]].push_back(i);
        ans[2] += c[i]+d[i];
    }


    dfs(1, 0);
    dfs2(dp2[1][1], 0);
    dfs3(1, 0, dp[1]);

    ans[1] = ans[2] - ans[1];
    ans[2] -= dp2[1][0];
    for(int i=3;i<=n;i++) {
        ans[i] = ans[i-1] - pq.top(), pq.pop();
    }

    cin >> m;
    while(m--) {
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

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