Submission #1159441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159441		knhatdev	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	176 ms	42700 KiB

designated_cities

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define ii pair<int, int>
#define iii pair<int, ii>
using namespace std;

const int N = 4e5 + 1;
int n, w[N], sum, ans[N], d[N], par[N], vis[N], pos;
vector<iii> a[N];
vector<int> chia;

void dfs1(int u, int cha) {
    for (iii v : a[u]) {
        if (v.fi == cha) continue;
        dfs1(v.fi, u);
        w[u] += w[v.fi] + v.se.se;
    }
}

void reroot(int u, int cha) {
    for (iii v : a[u]) {
        if (v.fi == cha) continue;
        w[v.fi] = w[u] - v.se.se + v.se.fi;
        reroot(v.fi, u);
    }
}

void dfs2(int u, int cha) {
    par[u] = cha;
    for (iii v : a[u]) {
        if (v.fi == cha) continue;
        d[v.fi] = d[u] + v.se.fi + v.se.se;
        dfs2(v.fi, u);
    }
}

int dfs3(int u, int cha) {
    int mx = 0;
    for (iii v : a[u]) {
        if (v.fi == cha) continue;
        int tmp = dfs3(v.fi, u) + v.se.fi;
        if (!mx) mx = tmp;
        else {
            chia.push_back(min(mx, tmp));
            mx = max(mx, tmp);
        }
    }
    return mx;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v, d, c;
        cin >> u >> v >> d >> c;
        a[u].push_back({v, {d, c}});
        a[v].push_back({u, {c, d}});
        sum += d + c;
    }
    dfs1(1, -1);
    reroot(1, -1);

    int l = 1, r = 1;
    dfs2(1, -1);
    for (int i = 1; i <= n; i++) {
        if (w[i] + d[i] > w[l] + d[l]) l = i;
        ans[1] = max(ans[1], w[i]);
    }

    d[l] = 0;
    dfs2(l, -1);
    for (int i = 1; i <= n; i++) {
        if (w[i] + d[i] > w[r] + d[r]) r = i;
    }

    ans[2] = (w[l] + w[r] + d[r]) / 2;

    int u = r;
    pos = 2;
    while (u != -1) {
        vis[u] = true;
        u = par[u];
    }

    u = r;
    while (u != -1) {
        for (iii v : a[u]) {
            if (vis[v.fi]) continue;
            chia.push_back(dfs3(v.fi, u) + v.se.fi);
        }
        u = par[u];
    }

    sort(chia.begin(), chia.end(), greater<int>());
    for (int x : chia) {
        pos++;
        ans[pos] = ans[pos - 1] + x;
    }

    while (pos < n) {
        pos++;
        ans[pos] = sum;
    }

    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        cout << sum - ans[k] << '\n';
    }
}

Compilation message (stderr)

designated_cities.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main() {
      | ^~~~

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