Submission #894009

#	Time	Username	Problem	Language	Result	Execution time	Memory
894009		box	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	717 ms	38352 KiB

designated_cities

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int MAXN = 2e5;

int N;
int W[MAXN * 2];
vector<pii> adj[MAXN];
i64 sum_in[MAXN];
i64 tot, save[MAXN + 1];

namespace S {
void dfs1(int p, int i) {
    for (auto [j, h] : adj[i]) if (p != j) {
        dfs1(i, j);
        sum_in[i] += sum_in[j] + W[h ^ 1];
    }
}
void dfs2(int p, int i) {
    for (auto [j, h] : adj[i]) if (p != j) {
        sum_in[j] = sum_in[i] - W[h ^ 1] + W[h];
        dfs2(i, j);
    }
}
}

namespace C {
bool done[MAXN];
int sz[MAXN];
vector<i64> paths, best;
int dfs_sz(int p, int i) {
    sz[i] = 1;
    for (auto [j, h] : adj[i]) if (p != j && !done[j])
        sz[i] += dfs_sz(i, j);
    return sz[i];
}
int dfs_cen(int p, int i, int s) {
    for (auto [j, h] : adj[i]) if (p != j && !done[j] && sz[j] * 2 > s)
        return dfs_cen(i, j, s);
    return i;
}
i64 make_paths(int p, int i) {
    i64 top = 0;
    for (auto [j, h] : adj[i]) if (p != j && !done[j]) {
        i64 x = make_paths(i, j) + W[h];
        if (x > top) {
            if (top > 0) paths.push_back(top);
            top = x;
        } else {
            paths.push_back(x);
        }
    }
    return top;
}
void decomp(int i) {
    i = dfs_cen(-1, i, dfs_sz(-1, i));
    done[i] = 1;
    for (auto [j, h] : adj[i]) if (!done[j]) {
        i64 x = make_paths(i, j) + W[h];
        paths.push_back(x);
        best.push_back(x);
    }
    sort(rbegin(paths), rend(paths));
    sort(rbegin(best), rend(best));
    {
        i64 x = sum_in[i]; int c = 1;
        save[c] = max(save[c], x);
        for (i64 y : paths) {
            x += y, c++;
            save[c] = max(save[c], x);
        }
    }
    if (sz(best) >= 2) {
        i64 x = sum_in[i] + best[0] + best[1]; int c = 2;
        paths.erase(find(begin(paths), end(paths), best[0]));
        paths.erase(find(begin(paths), end(paths), best[1]));
        save[c] = max(save[c], x);
        for (i64 y : paths) {
            x += y, c++;
            save[c] = max(save[c], x);
        }
    }
    exchange(paths, {});
    exchange(best, {});
    for (auto [j, h] : adj[i]) if (!done[j]) decomp(j);
}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int h = 0; h < N - 1; h++) {
        int i, j;
        cin >> i >> j, i--, j--;
        cin >> W[h * 2] >> W[h * 2 + 1];
        adj[i].push_back({j, h * 2});
        adj[j].push_back({i, h * 2 + 1});
        tot += W[h * 2] + W[h * 2 + 1];
    }
    S::dfs1(-1, 0);
    S::dfs2(-1, 0);
    C::decomp(0);
    for (int i = 1; i <= N; i++) save[i] = max(save[i], save[i - 1]);
    int Q;
    cin >> Q;
    while (Q--) {
        int k;
        cin >> k;
        cout << tot - save[k] << '\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