oj.uz

Submission #853758

# Submission time Handle Problem Language Result Execution time Memory
853758 2023-09-25T07:47:19 Z FairyWinx Closing Time (IOI23_closing) C++17
26 / 100
 146 ms 39828 KB 
#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);
}

pair<set<pair<long long, int>>, set<pair<long long, int>>> build(long long k, vector<pair<long long, int>> &value1, 
            vector<pair<long long, int>> &value2, vector<long long> &dist1, vector<long long> &dist2) {
    sort(rall(value1));
    sort(rall(value2));
    vector<pair<int, int>> ans;
    set<pair<long long, int>> used1, used2;
    while (value1.size() || value2.size()) {
        if (!value1.size()) {
            if (value2.back().first > k) {
                break;
            } else {
                int v = value2.back().second;
                used2.emplace(max(dist1[v], dist2[v]), v);
                k -= value2.back().first;
                value2.pop_back();
            }
        } else if (!value2.size()) {
            if (value1.back().first > k) {
                break;
            } else {
                int v = value1.back().second;
                used1.emplace(abs(dist1[v] - dist2[v]), v);
                k -= value1.back().first;
                value1.pop_back();
            }
        } else {
            if (k >= value1.back().first && (k < value2.back().first || 
                    (2 * value1.back().first < value2.back().first))) {
 
                // value1 оптимальнее
                int v = value1.back().second;
                used1.emplace(abs(dist1[v] - dist2[v]), v);
                k -= value1.back().first;
                value1.pop_back();
            } else if (k >= value2.back().first) {
                int v = value2.back().second;
                used2.emplace(max(dist1[v], dist2[v]), v);
                k -= value2.back().first;
                value2.pop_back();
            } else {
                break;
            }
        }
    }
    return {used1, used2};
}

void update_ans(long long k, long long &cur_sum, set<pair<long long, int>> &used1, 
                set<pair<long long, int>> &used2, set<pair<long long, int>> &unused1, 
                set<pair<long long, int>> &unused2) {

    // aboba
    while (cur_sum > k) {
        if (!used1.size()) {
            cur_sum -= used2.rbegin()->first;
            unused2.emplace(*used2.rbegin());
            used2.erase(*used2.rbegin());
        } else if (!used2.size()) {
            cur_sum -= used1.rbegin()->first;
            unused1.emplace(*used1.rbegin());
            used1.erase(*used1.rbegin());
        } else {
            if (used1.rbegin()->first * 2 < used2.rbegin()->first) {
                cur_sum -= used2.rbegin()->first;
                unused2.emplace(*used2.rbegin());
                used2.erase(*used2.rbegin());
            } else {
                cur_sum -= used1.rbegin()->first;
                unused1.emplace(*used1.rbegin());
                used1.erase(*used1.rbegin());
            }
        }
    }
    if (unused1.size() && k - cur_sum >= unused1.begin()->first) {
        cur_sum += unused1.begin()->first;
        used1.insert(*unused1.begin());
        unused1.erase(unused1.begin());
    }
}

int get_ans(long long k, long long cur_sum, set<pair<long long, int>> &used1, set<pair<long long, int>> &used2, 
            set<pair<long long, int>> &unused2) {

    if (used1.size() && unused2.size()) {
        if (k - cur_sum + used1.rbegin()->first >= unused2.begin()->first) {
            return used1.size() + used2.size() * 2 + 1;
        }
    }
    return used1.size() + used2.size() * 2;
}

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<pair<long long, int>> value;
    for (int i = 0; i < n; ++i) {
        value.emplace_back(dist1[i], i);
        value.emplace_back(dist2[i], i);
    }
    sort(all(value));
    int ans = 0;
    {
        vector<int> used(n);
        long long sum = 0;
        int cnt = 0;
        for (auto c : value) {
            if (used[c.second])
                continue;
            sum += c.first;
            ++cnt;
            used[c.second] = 1;
            if (sum > k)
                break;
            ans = max(ans, cnt);
        }
    }

    vector<int> path;
    {
        vector<int> par(n);
        dfs_find_par(x, -1, par);
        int tmp = y;
        while (tmp != -1) {
            path.push_back(tmp);
            tmp = par[tmp];
        }
    }
    vector<int> used(n);
    int cnt = 0;
    for (int v : path) {
        k -= min(dist1[v], dist2[v]);
        ++cnt;
        used[v] = 1;
    }
    if (k < 0)
        return ans;

    vector<pair<long long, int>> value1, value2;
    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            value1.emplace_back(abs(dist1[i] - dist2[i]), i);
        } else {
            value2.emplace_back(max(dist1[i], dist2[i]), i);
        }
    }
    auto [used1, used2] = build(k, value1, value2, dist1, dist2);
    set<pair<long long, int>> unused1;
    set<pair<long long, int>> unused2;
    {
        vector<int> in_ans(n);
        for (auto i : used2)
            in_ans[i.second] = 1;
        for (int i = 0; i < n; ++i) {
            if (!in_ans[i] && !used[i]) {
                unused2.emplace(max(dist1[i], dist2[i]), i);
            }
        }
    }
    {
        vector<int> in_ans(n);
        for (auto i : used1)
            in_ans[i.second] = 1;
        for (int i = 0; i < n; ++i) {
            if (!in_ans[i] && used[i]) {
                unused1.emplace(abs(dist1[i] - dist2[i]), i);
            }
        }
    }
    long long cur_sum = 0;
    for (auto i : used1)
        cur_sum += i.first;
    for (auto i : used2)
        cur_sum += i.first;
    ans = max(ans, cnt + get_ans(k, cur_sum, used1, used2, unused2));
    for (auto c : value) {
        if (used[c.second])
            continue;
        used[c.second] = 1;
        ++cnt;
        k -= c.first;
        if (k < 0)
            break;
        if (used2.count(make_pair(max(dist1[c.second], dist2[c.second]), c.second)))
            cur_sum -= max(dist1[c.second], dist2[c.second]);

        used2.erase(make_pair(max(dist1[c.second], dist2[c.second]), c.second));
        unused2.erase(make_pair(max(dist1[c.second], dist2[c.second]), c.second));
        unused1.emplace(abs(dist1[c.second] - dist2[c.second]), c.second);
        update_ans(k, cur_sum, used1, used2, unused1, unused2);
        ans = max(ans, cnt + get_ans(k, cur_sum, used1, used2, unused2));
    }

    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 34112 KB Output is correct
2 Correct 146 ms 39828 KB Output is correct
3 Correct 84 ms 2900 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 504 KB Output is correct
21 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '884', found: '873'
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 504 KB Output is correct
21 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '884', found: '873'
22 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 344 KB Output is correct
45 Correct 1 ms 344 KB Output is correct
46 Correct 0 ms 600 KB Output is correct
47 Correct 1 ms 344 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '51', found: '50'
50 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '884', found: '873'
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '884', found: '873'
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '884', found: '873'
23 Halted 0 ms 0 KB -