Submission #853428

#	Time	Username	Problem	Language	Result	Execution time	Memory
853428		FairyWinx	Closing Time (IOI23_closing)	C++17	9 / 100	1029 ms	37808 KiB

closing

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

vector<vector<pair<int, int>>> G;
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);
        }
    }
}

void dfs_find_par(int v, int p, vector<int> &par) {
    par[v] = p;
    for (auto i : G[v]) {
        if (i.first != p) {
            dfs_find_par(i.first, v, par);
        }
    }
}

void init(int n) {
    G.clear();
    ban.clear();;

    G.resize(n);
    ban.resize(n);
}

void dfs(int v, int par, long long d, vector<pair<long long, int>> &value) {
    if (!ban[v])
        value.emplace_back(d, v);
    for (auto i : G[v]) {
        if (i.first == par || ban[i.first])
            continue;
        dfs(i.first, v, d + i.second, value);
    }
}

int solve(int n, int l, int r, long long k, vector<int> &path, vector<long long> &dist1, 
            vector<long long> &dist2, int x, int y) {

    fill(all(ban), 0);
    for (int i = l; i < r; ++i) {
        ban[path[i]] = 1;
    }
    vector<pair<long long, int>> value1;
    vector<pair<long long, int>> value2;
    // добавить иф, чтобы не добавлялись единицы, если забанены эти вершины
    if (r != (int) path.size())
        dfs(x, -1, 0, value1);
    if (l != 0)
        dfs(y, -1, 0, value1);
    long long sum = 0;
    vector<pair<int, int>> ans; // добавить эти вершины в самом начале
    int cnt = 0;
    for (int i : path) {
        if (ban[i]) {
            if (l != r) {
                cnt += 2;
                ans.emplace_back(i, 2);
                sum += max(dist1[i], dist2[i]);
            }
        } else {
            if (l != r) {
                cnt += 1;
                ans.emplace_back(i, 1);
                sum += min(dist1[i], dist2[i]);
            }
        }
    }
    for (int i : path)
        ban[i] = 1;
    // cout << sum << ' ' << k << '\n';
    vector<int> used(n);
    if (l != r) {
        for (int i : path) {
            used[i] = 1;
        }
    }
    if (sum > k)
        return -1;
    else
        k -= sum;
    
    int aboba = 0;
    for (int i = l; i < r; ++i) {
        dfs(path[i], -1, max(dist1[path[i]], dist2[path[i]]), value2);
    }
    sort(all(value1));
    sort(all(value2));
    for (int i1 = 0; i1 <= (int) value1.size(); ++i1) {
        for (int i2 = 0; i2 <= (int) value2.size(); ++i2) {
            vector<int> used(n);
            long long sum = 0;
            int _cnt = cnt;
            if (l != r) {
                for (int i : path)
                    used[i] = 1;
            }
            for (int i = 0; i < i1; ++i) {
                if (used[value1[i].second])
                    continue;
                used[value1[i].second] = 1;
                sum += value1[i].first;
                ++_cnt;
            }
            for (int i = 0; i < i2; ++i) {
                if (used[value2[i].second])
                    continue;
                used[value2[i].second] = 1;
                sum += value2[i].first;
                _cnt += 2;
            }
            // cout << l << ' ' << r << ' ' << i1 << ' ' << i2 << ' ' << sum << ' ' << _cnt << '\n';
            if (sum <= k) {
                aboba = max(aboba, _cnt);
            }
        }
    }
    return aboba;

    // for (int i = l; i < r; ++i) {
    //     dfs(path[i], -1, max(dist1[path[i]], dist2[path[i]]), value2);
    // }
    // sort(rall(value1));
    // sort(rall(value2));
    // // for (auto i : value1) {
    // //     cout << i.first << ' ' << i.second << '\n';
    // // }
    // while (value1.size() || value2.size()) {
    //     if (value1.size() && used[value1.back().second]) {
    //         value1.pop_back();
    //         continue;
    //     } else if (value2.size() && used[value2.back().second]) {
    //         value2.pop_back();
    //         continue;
    //     }
    //     // добавить used, чтобы вершина не бралась дважды + не брать на пути.
    //     if (!value1.size()) {
    //         if (value2.back().first > k) {
    //             break;
    //         } else {
    //             ans.emplace_back(value2.back().second, 2);
    //             k -= value2.back().first;
    //             used[value2.back().second] = 1;
    //             value2.pop_back();
    //         }
    //     } else if (!value2.size()) {
    //         if (value1.back().first > k) {
    //             break;
    //         } else {
    //             ans.emplace_back(value1.back().second, 1);
    //             k -= value1.back().first;
    //             used[value1.back().second] = 1;
    //             value1.pop_back();
    //         }
    //     } else {
    //         if (k >= value1.back().first && (k < value2.back().first || 
    //                 (2 * value1.back().first < value2.back().first))) {

    //             // value1 оптимальнее
    //             ans.emplace_back(value1.back().second, 1);
    //             k -= value1.back().first;
    //             used[value1.back().second] = 1;
    //             value1.pop_back();
    //         } else if (k >= value2.back().first) {
    //             ans.emplace_back(value2.back().second, 2);
    //             k -= value2.back().first;
    //             used[value2.back().second] = 1;
    //             value2.pop_back();
    //         } else {
    //             break;
    //         }
    //     }
    // }
    // while (value2.size() && used[value2.back().second]) {
    //     value2.pop_back();
    // }
    // if (value2.size()) {
    //     for (int i = (int) ans.size() - 1; i >= 0; --i) {
    //         if (ans[i].second == 1) {
    //             if (k + min(dist1[ans[i].first], dist2[ans[i].first]) >= value2.back().first) {
    //                 swap(ans[i], ans.back());
    //                 ans.pop_back();
    //                 ans.emplace_back(value2.back().second, 2);
    //                 value2.pop_back();
    //             }

    //             break;
    //         }
    //     }
    // }
    // int cnt = 0;
    // for (auto i : ans) {
    //     cnt += i.second;
    // }
    // return cnt;
}

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

    init(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);

    vector<int> path;
    {
        vector<int> par(n);
        dfs_find_par(x, -1, par);
        int tmp = y;
        while (tmp != x) {
            path.push_back(tmp);
            tmp = par[tmp];
        }
        path.push_back(tmp);
    }

    int ans = solve(n, -1, -1, k, path, dist1, dist2, x, y);

    for (int l = 0; l < (int) path.size(); ++l) {
        for (int r = l + 1; r <= (int) path.size(); ++r) {
            ans = max(ans, solve(n, l, r, k, path, dist1, dist2, x, y));
            // cout << l << ' ' << r << ' ' << solve(n, l, r, k, path, dist1, dist2, x, y) << '\n';
        }
    }
    // return solve(n, 1, 3, k, path, dist1, dist2, x, y);
    return ans;
}

#ifdef LOCAL

int main()
{
    // BEGIN SECRET
    {
        std::string in_secret = "cc61ad56a4797fb3f5c9529f73ce6fcedd85669b";
        std::string out_secret = "081ce3c351cbf526b37954b9ad30f2b531a7585c";
        char secret[1000];
        assert(1 == scanf("%s", secret));
        if (std::string(secret) != in_secret)
        {
            printf("%s\n", out_secret.c_str());
            printf("SV\n");
            fclose(stdout);
            return 0;
        }
    }
    // END SECRET

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    // BEGIN SECRET
    {
        std::string out_secret = "081ce3c351cbf526b37954b9ad30f2b531a7585c";
        printf("%s\n", out_secret.c_str());
        printf("OK\n");
    }
    // END SECRET
    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}

#endif

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