Submission #1211629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211629		mar	Closing Time (IOI23_closing)	C++20	8 / 100	94 ms	25528 KiB

closing

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

#define ll long long

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    vector<vector<pair<int, int>>> g(n);
    for(int i = 0; i < n - 1; i++) {
        g[u[i]].push_back({v[i], w[i]});
        g[v[i]].push_back({u[i], w[i]});
    }

    vector<ll> dx(n, -1), dy(n, -1);
    dx[x] = 0;
    dy[y] = 0;

    queue<pair<int, int>> q;
    q.push({x, 0});
    q.push({y, 1});

    while(!q.empty()) {
        int cur = q.front().first;
        int s = q.front().second;
        q.pop();
        for (auto next : g[cur]) {
            int to = next.first;
            int cost = next.second;
            if (s == 0 && dx[to] == -1) {
                dx[to] = dx[cur] + cost;
                q.push({to, s});
            }
            if (s == 1 && dy[to] == -1) {
                dy[to] = dy[cur] + cost;
                q.push({to, s});
            }
        }
    }

    ll res = 0;
    vector<ll> c1(n), c2(n);
    priority_queue<ll> pq;

    for(int i = 0; i < n; i++) {
        c1[i] = min(dx[i], dy[i]);
        c2[i] = max(dx[i], dy[i]);
        pq.push(-c1[i]);
        if (dx[i] + dy[i] == dx[y]) {
            res += c1[i];
            c2[i] -= c1[i];
            c1[i] = 0;
        }
    }

    int ans = 0;
    ll rem = k;
    while(!pq.empty() && rem >= -pq.top()) {
        rem += pq.top();
        pq.pop();
        ans++;
    }

    return ans;
}

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