oj.uz

Submission #992737

# Submission time Handle Problem Language Result Execution time Memory
992737 2024-06-05T06:35:15 Z stdfloat Closing Time (IOI23_closing) C++17
9 / 100
 448 ms 29016 KB 
#include <bits/stdc++.h>
#include "closing.h"
using namespace std;

#define ff  first
#define ss  second
#define pii pair<int, int>

using ll = long long;

vector<bool> vis;

vector<ll> c;

vector<vector<pii>> E;

bool dfs(int x, int p = -1, ll sm = 0) {
    bool tr = false;

    if (vis[x]) {
        tr = true;
        c[x] = max(c[x], sm);
    }

    for (auto [i, w] : E[x]) {
        if (i != p && dfs(i, x, sm + w)) {
            tr = true;
            c[x] = max(c[x], sm);
        }
    }

    return tr;
}

int max_score(int n, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    E.assign(n, {});
    for (int i = 0; i < n - 1; i++) {
        E[U[i]].push_back({V[i], W[i]});
        E[V[i]].push_back({U[i], W[i]});
    }

    auto f = [&](int st) -> vector<ll> {
        queue<int> q;
        vector<ll> dis(n, -1);
        q.push(st); dis[st] = 0;
        while (!q.empty()) {
            auto x = q.front(); q.pop();

            for (auto [i, w] : E[x]) {
                if (dis[i] == -1) {
                    dis[i] = dis[x] + w;
                    q.push(i);
                }
            }
        }

        return dis;
    };

    vector<ll> disx = f(X), disy = f(Y);

    vector<pii> u;
    for (int i = 0; i < n; i++)
        u.push_back({min(disx[i], disy[i]), i});

    sort(u.begin(), u.end());

    int mx = 0;
    for (int mk = 0; mk < 1 << n; mk++) {
        c.assign(n, -1);
        vis.assign(n, false);
        for (int i = 0; i < n; i++)
            vis[i] = (mk >> i) & 1;

        dfs(X); dfs(Y);

        ll sm = 0;
        int cnt = 0;
        for (int i = 0; i < n && sm <= K; i++) {
            if (c[i] != -1) {
                sm += c[i];
                cnt += 1 + (c[i] == max(disx[i], disy[i]));
            }
        }

        if (sm > K) continue;

        for (int i = 0; i < n; i++) {
            if (c[u[i].ss] == -1) {
                if ((sm += u[i].ff) > K) break;
                cnt += 1 + (disx[u[i].ss] == disy[u[i].ss]);
            }
        }

        mx = max(mx, cnt);
    }

    return mx;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 29016 KB 1st lines differ - on the 1st token, expected: '451', found: '200000'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 386 ms 416 KB Output is correct
3 Correct 400 ms 592 KB Output is correct
4 Correct 423 ms 344 KB Output is correct
5 Correct 190 ms 404 KB Output is correct
6 Correct 273 ms 344 KB Output is correct
7 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 386 ms 416 KB Output is correct
3 Correct 400 ms 592 KB Output is correct
4 Correct 423 ms 344 KB Output is correct
5 Correct 190 ms 404 KB Output is correct
6 Correct 273 ms 344 KB Output is correct
7 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
8 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 386 ms 416 KB Output is correct
3 Correct 400 ms 592 KB Output is correct
4 Correct 423 ms 344 KB Output is correct
5 Correct 190 ms 404 KB Output is correct
6 Correct 273 ms 344 KB Output is correct
7 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
8 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 386 ms 416 KB Output is correct
4 Correct 400 ms 592 KB Output is correct
5 Correct 423 ms 344 KB Output is correct
6 Correct 190 ms 404 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 82 ms 348 KB Output is correct
11 Correct 181 ms 344 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 378 ms 408 KB Output is correct
14 Correct 180 ms 408 KB Output is correct
15 Correct 84 ms 408 KB Output is correct
16 Correct 90 ms 412 KB Output is correct
17 Correct 78 ms 344 KB Output is correct
18 Correct 175 ms 344 KB Output is correct
19 Correct 375 ms 344 KB Output is correct
20 Correct 87 ms 404 KB Output is correct
21 Correct 82 ms 348 KB Output is correct
22 Correct 384 ms 408 KB Output is correct
23 Correct 448 ms 416 KB Output is correct
24 Correct 83 ms 408 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 386 ms 416 KB Output is correct
4 Correct 400 ms 592 KB Output is correct
5 Correct 423 ms 344 KB Output is correct
6 Correct 190 ms 404 KB Output is correct
7 Correct 273 ms 344 KB Output is correct
8 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 386 ms 416 KB Output is correct
4 Correct 400 ms 592 KB Output is correct
5 Correct 423 ms 344 KB Output is correct
6 Correct 190 ms 404 KB Output is correct
7 Correct 273 ms 344 KB Output is correct
8 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 386 ms 416 KB Output is correct
4 Correct 400 ms 592 KB Output is correct
5 Correct 423 ms 344 KB Output is correct
6 Correct 190 ms 404 KB Output is correct
7 Correct 273 ms 344 KB Output is correct
8 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
9 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 386 ms 416 KB Output is correct
4 Correct 400 ms 592 KB Output is correct
5 Correct 423 ms 344 KB Output is correct
6 Correct 190 ms 404 KB Output is correct
7 Correct 273 ms 344 KB Output is correct
8 Incorrect 31 ms 348 KB 1st lines differ - on the 1st token, expected: '26', found: '17'
9 Halted 0 ms 0 KB -