oj.uz

Submission #840828

# Submission time Handle Problem Language Result Execution time Memory
840828 2023-08-31T18:14:00 Z vjudge1 Closing Time (IOI23_closing) C++17
8 / 100
 133 ms 36752 KB 
#include "closing.h"

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

vector<pair<int, int>> adj[200000];

void dfs(int u, int p, vector<int64_t>& d) {
        for (auto [v, c] : adj[u]) {
                if (v == p) continue;
                d[v] = d[u] + c;
                dfs(v, u, d);
        }
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
        for (int i = 0; i < N; i++) adj[i].clear();
        for (int i = 0; i < N - 1; i++) {
                adj[U[i]].emplace_back(V[i], W[i]);
                adj[V[i]].emplace_back(U[i], W[i]);
        }
        vector<int64_t> dX(N), dY(N);
        dfs(X, -1, dX);
        dfs(Y, -1, dY);
        vector<int> ord(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return max(dX[i], dY[i]) < max(dX[j], dY[j]);
        });
        vector<int> path;
        for (int i = 0; i < N; i++) {
                if (dX[i] + dY[i] == dX[Y]) path.emplace_back(i);
        }
        vector<int> both(N, 0);
        vector<int> chk;
        int64_t cur = 0;

        auto solve = [&](bool con = 1) {
                if (cur > K) return -N * 2;
                int cnt = 0;
                int64_t cost = cur;
                vector<int> c(N, 0);
                vector<int> vis(N, 0);
                if (con) {
                        for (int x : path) {
                                if (both[x]) continue;
                                cost += min(dX[x], dY[x]);
                                c[x] = 1;
                                cnt++;
                        }
                        if (cost > K) return -N * 2;
                        queue<int> q;
                        for (int i : chk) {
                                cnt += 2;
                                q.emplace(i);
                                vis[i] = 1;
                        }
                        while (q.size()) {
                                int u = q.front();
                                q.pop();
                                for (auto [v, w] : adj[u]) {
                                        if (vis[v]) continue;
                                        if (c[v]) continue;
                                        if (dX[v] == dX[u] + w && dY[v] == dY[u] + w) {
                                                q.emplace(v);
                                                vis[v] = 1;
                                        }
                                }
                        }
                }
                priority_queue<pair<int64_t, int>> pq2, pq1;
                for (int i = 0; i < N; i++) {
                        if (both[i]) continue;
                        if (c[i]) continue;
                        if (vis[i]) {
                                pq2.emplace(-max(dX[i], dY[i]), i);
                        } else {
                                pq1.emplace(-min(dX[i], dY[i]), i);
                        }
                }
                vector<int> order;
                while (pq2.size()) {
                        auto [du, u] = pq2.top();
                        if (cost - du > K) break;
                        pq2.pop();
                        cost -= du;
                        order.emplace_back(u);
                        cnt += 2;
                }
                while (pq2.size()) pq1.emplace(pq2.top()), pq2.pop();
                auto upd = [&]() {
                        while (pq1.size()) {
                                auto [du, u] = pq1.top();
                                if (cost - du > K) return;
                                pq1.pop();
                                cost -= du;
                                c[u] = 1;
                                cnt++;
                        }
                };
                upd();
                int ans = cnt;
                while (order.size()) {
                        cnt -= 2;
                        int u = order.back();
                        order.pop_back();
                        cost -= max(dX[u], dY[u]);
                        pq1.emplace(-min(dX[u], dY[u]), u);
                        upd();
                        ans = max(ans, cnt);
                }
                return ans;
        };

        int res = solve(0);
        for (int i = 0; i < N; i++) {
                int j = ord[i];
                if (dX[j] + dY[j]) {
                        chk.emplace_back(j);
                        both[j] = 1;
                        cur += max(dX[j], dY[j]);
                        res = max(res, solve());
                }
        }
        return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 32160 KB Output is correct
2 Correct 133 ms 36752 KB Output is correct
3 Correct 67 ms 7684 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
10 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
10 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
10 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '74', found: '73'
10 Halted 0 ms 0 KB -