oj.uz

Submission #998889

# Submission time Handle Problem Language Result Execution time Memory
998889 2024-06-14T19:17:14 Z Wael Closing Time (IOI23_closing) C++17
17 / 100
 782 ms 69696 KB 
#include "closing.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W) {
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }

    vector<vector<i64>> dis(n, vector<i64>(2, 0));
    vector<vector<int>> next(n, vector<int>(2, -1));
    function<void(int, int, int)> dfs = [&](int u, int p, int t) {
        for (auto [v, w] : adj[u]) {
            if (v == p) continue;
            dis[v][t] = dis[u][t] + w;
            next[v][!t] = u;
            dfs(v, u, t);
        }
    };
    dfs(x, -1, 0);
    dfs(y, -1, 1);

    i64 pathCost = 0;
    vector<int> path, onPath(n, 0);
    int z = x;
    while (true) {
        path.push_back(z);
        onPath[z] = 1;
        pathCost += min(dis[z][0], dis[z][1]);
        if (z == y) {
            break;
        }
        z = next[z][0];
    }
    
    vector<pair<i64, int>> vec;
    vector<i64> one(n), two(n);
    for (int u = 0; u < n; ++u) {
        one[u] = min(dis[u][0], dis[u][1]);
        two[u] = max(dis[u][0], dis[u][1]);
        vec.push_back({two[u], u});
    }
    sort(vec.begin(), vec.end(), greater<pair<i64, int>>());

    vector<int> used(n, 0);
    auto work = [&](bool mark, i64 k) {
        int ret = 0;
        vector<int> vis = used;
        if (mark) {
            for (auto u : path) {
                if (vis[u] == 0) {
                    vis[u] = 1;
                    k -= one[u];
                    ++ret;
                }
            }
        } else {
            vis[x] = vis[y] = 1;
            ret = 2;
        }
        if (k < 0) {
            return (int)-1e9;
        }

        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
        for (int u = 0; u < n; ++u) {
            bool found = 0;
            for (auto [v, w] : adj[u]) {
                found |= vis[v];
            }
            if (found) {
                pq.push({one[u], u});
            }
        }

        while (pq.size()) {
            auto [cost, u] = pq.top();
            pq.pop();
            if (cost > k) {
                break;
            }
            if (vis[u]) {
                continue;
            }

            vis[u] = 1;        
            k -= cost;
            ++ret;
            for (auto [v, w] : adj[u]) {
                pq.push({one[v], v});
            }
        }

        return ret;
    };

    auto canMark = [&](int u, i64 k, i64 pathCost) {
        pathCost -= (onPath[u] ? one[u] : 0);
        k -= two[u];
        return k >= pathCost;
    };

    int ans = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        fill(used.begin(), used.end(), 0);

        i64 curK = k;
        for (int j = 0; j < n; ++j) {
            if (mask & (1 << j)) {
                used[j] = 1;
                curK -= two[j];
            }
        }
        int cnt = __builtin_popcount(mask);
        ans = max(ans, work(cnt > 0, curK) + 2 * cnt);
    }

    return ans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:101:10: warning: variable 'canMark' set but not used [-Wunused-but-set-variable]
  101 |     auto canMark = [&](int u, i64 k, i64 pathCost) {
      |          ^~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 60100 KB Output is correct
2 Correct 186 ms 69696 KB Output is correct
3 Correct 173 ms 5716 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 545 ms 436 KB Output is correct
3 Correct 202 ms 348 KB Output is correct
4 Correct 296 ms 344 KB Output is correct
5 Correct 75 ms 348 KB Output is correct
6 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
7 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 545 ms 436 KB Output is correct
3 Correct 202 ms 348 KB Output is correct
4 Correct 296 ms 344 KB Output is correct
5 Correct 75 ms 348 KB Output is correct
6 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
7 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 545 ms 436 KB Output is correct
3 Correct 202 ms 348 KB Output is correct
4 Correct 296 ms 344 KB Output is correct
5 Correct 75 ms 348 KB Output is correct
6 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
7 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 545 ms 436 KB Output is correct
4 Correct 202 ms 348 KB Output is correct
5 Correct 296 ms 344 KB Output is correct
6 Correct 75 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 22 ms 412 KB Output is correct
11 Correct 240 ms 428 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 493 ms 348 KB Output is correct
14 Correct 344 ms 416 KB Output is correct
15 Correct 23 ms 348 KB Output is correct
16 Correct 183 ms 344 KB Output is correct
17 Correct 22 ms 344 KB Output is correct
18 Correct 59 ms 436 KB Output is correct
19 Correct 118 ms 348 KB Output is correct
20 Correct 150 ms 348 KB Output is correct
21 Correct 69 ms 412 KB Output is correct
22 Correct 764 ms 416 KB Output is correct
23 Correct 782 ms 600 KB Output is correct
24 Correct 21 ms 348 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 545 ms 436 KB Output is correct
4 Correct 202 ms 348 KB Output is correct
5 Correct 296 ms 344 KB Output is correct
6 Correct 75 ms 348 KB Output is correct
7 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
8 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 545 ms 436 KB Output is correct
4 Correct 202 ms 348 KB Output is correct
5 Correct 296 ms 344 KB Output is correct
6 Correct 75 ms 348 KB Output is correct
7 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
8 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 545 ms 436 KB Output is correct
4 Correct 202 ms 348 KB Output is correct
5 Correct 296 ms 344 KB Output is correct
6 Correct 75 ms 348 KB Output is correct
7 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
8 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 545 ms 436 KB Output is correct
4 Correct 202 ms 348 KB Output is correct
5 Correct 296 ms 344 KB Output is correct
6 Correct 75 ms 348 KB Output is correct
7 Incorrect 679 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '50'
8 Halted 0 ms 0 KB -