Submission #1011082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011082		aaaaaarroz	봉쇄 시간 (IOI23_closing)	C++17	35 / 100	1031 ms	50012 KiB

closing

    #include "closing.h"
    #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));
        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;
                dfs(v, u, t);
            }
        };
        dfs(x, -1, 0);
        dfs(y, -1, 1);
        int ans = 2;
        vector<vector<int>> used(n, vector<int>(2, 0));
        used[x][0] = 1;
        used[y][1] = 1;
        for (int c = 1; c <= 2 * n; ++c) {
            i64 mn = 1e18;
            int from, type;
            for (int u = 0; u < n; ++u) {
                for (auto [v, w] : adj[u]) {
                    for (int t = 0; t <= 1; ++t) {
                        if (used[v][t] && used[u][t] == 0) {
                            if (mn > dis[u][t]) {
                                from = u;
                                type = t;
                            }
                            mn = min(mn, dis[u][t]);
                        }
                    }
                }
            }
            if (mn <= k) {
                k -= mn;
                used[from][type] = 1;
                dis[from][!type] -= mn;
                ++ans;
            } 
            else {
                break;
            }
        }
        return ans;
    }

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:43:32: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |                 used[from][type] = 1;
      |                                ^
closing.cpp:43:26: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |                 used[from][type] = 1;
      |                          ^

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