Submission #1207383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207383		HappyCapybara	Closing Time (IOI23_closing)	C++17	8 / 100	78 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, s = q.front().second;
        q.pop();
        for (pair<int,int> next : G[cur]){
            if (s == 0 && dx[next.first] == -1){
                dx[next.first] = dx[cur]+(ll)next.second;
                q.push({next.first, s});
            }
            if (s == 1 && dy[next.first] == -1){
                dy[next.first] = dy[cur]+(ll)next.second;
                q.push({next.first, 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