Submission #852897

#	Time	Username	Problem	Language	Result	Execution time	Memory
852897		FairyWinx	Closing Time (IOI23_closing)	C++17	29 / 100	261 ms	49348 KiB

closing

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()

using namespace std;

vector<vector<pair<int, int>>> G;

const long long inf = 1'000'000'000'000'000'228ll;
vector<int> ban;

void dfs_calc_dist(int v, int par, long long d, vector<long long> &dist) {
    dist[v] = d;
    for (auto i : G[v]) {
        if (i.first != par) {
            dfs_calc_dist(i.first, v, d + i.second, dist);
        }
    }
}

bool dfs(int v, int par, long long d, long long &sum, vector<pair<long long, int>> &val, int &cnt) {
    bool find_ban = false;
    if (ban[v])
        find_ban = true;
    for (auto i : G[v]) {
        if (i.first != par) {
            if (dfs(i.first, v, d + i.second, sum, val, cnt)) {
                find_ban = true;
            }
        }
    }
    if (find_ban) {
        ++cnt;
        if (!ban[v]) {
            sum += d;
        }
    } else {
        val.emplace_back(d, v);
    }
    return find_ban;
}

int max_score(int n, int x, int y, long long k, 
    vector<int> u, vector<int> v, vector<int> w) {

    G.clear();
    G.resize(n);
    ban.clear();
    ban.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        G[u[i]].emplace_back(v[i], w[i]);
        G[v[i]].emplace_back(u[i], w[i]);
    }

    vector<long long> dist1(n), dist2(n);
    dfs_calc_dist(x, -1, 0, dist1);
    dfs_calc_dist(y, -1, 0, dist2);
    array<long long, 3> min_vertex = {inf, inf, -1};
    for (int i = 0; i < n; ++i) {
        min_vertex = min(min_vertex, array<long long, 3> {abs(dist1[i] - dist2[i]), dist1[i], i});
    }
    int V = min_vertex[2];
    vector<long long> dist3(n);
    dfs_calc_dist(V, -1, 0, dist3);
    vector<pair<long long, int>> value;
    for (int i = 0; i < n; ++i) {
        value.emplace_back(dist3[i], i);
    }
    sort(all(value));
    long long cur_sum_value = 0;
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        vector<pair<long long, int>> val;
        long long sum = 0;
        int cnt = 0;
        dfs(x, -1, 0, sum, val, cnt);
        dfs(y, -1, 0, sum, val, cnt);
        vector<int> used(n);
        sort(all(val));
        if (sum + cur_sum_value <= k) {
            int cur_get = 0;
            ans = max(ans, cnt);
            for (auto j : val) {
                if (used[j.second])
                    continue;
                if (j.first + sum + cur_sum_value <= k) {
                    ++cur_get;
                    sum += j.first;
                    ans = max(ans, cnt + cur_get);
                }
            }
        } else {
            break;
        }
        if (i != n) {
            ban[value[i].second] = 1;
            cur_sum_value += max(dist1[value[i].second], dist2[value[i].second]);
        }
    }

    return ans;
}

#ifdef LOCAL
    int main() {
        int Q;
        cin >> Q;
        for (int i = 0; i < Q; ++i) {
            int n, x, y;
            long long k;
            cin >> n >> x >> y >> k;
            vector<int> u(n - 1), v(n - 1), w(n - 1);
            for (int j = 0; j < n - 1; ++j) {
                int a, b, c;
                cin >> a >> b >> c;
                u[j] = a, v[j] = b, w[j] = c;
            }
            cout << max_score(n, x, y, k, u, v, w) << '\n';
        }
    }
#endif

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17