Submission #1219160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219160		HappyCapybara	Closing Time (IOI23_closing)	C++17	100 / 100	180 ms	38732 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> pq1;
    set<pair<ll,int>> pq2, pq3;
    int ans2 = 0;
    vector<int> lv(N, 0);
    for (int i=0; i<N; i++){
        c1[i] = min(dx[i], dy[i]);
        c2[i] = max(dx[i], dy[i])-c1[i];
        pq1.push(-c1[i]);
        if (dx[i]+dy[i] == dx[Y]){
            res += c1[i];
            lv[i]++;
            ans2++;
            pq2.insert({c2[i], i});
        }
        else {
            if (c2[i] > c1[i]) pq2.insert({c1[i], i});
            else pq3.insert({c1[i]+c2[i], i});
        }
    }
    int ans = 0;
    ll rem = K;
    while (!pq1.empty() && rem >= -pq1.top()){
        rem += pq1.top();
        pq1.pop();
        ans++;
    }
    rem = K-res;
    while (pq2.size() >= 2 && pq3.size() >= 1){
        int opt1 = pq2.begin()->first + next(pq2.begin())->first, opt2 = pq3.begin()->first;
        if (rem < min(opt1, opt2)) break;
        if (opt1 < opt2){
            rem -= pq2.begin()->first;
            ans2++;
            int i = pq2.begin()->second;
            pq2.erase(pq2.begin());
            if (lv[i] == 0) pq2.insert({c2[i], i});
            lv[i]++;
        }
        else {
            rem -= pq3.begin()->first;
            ans2 += 2;
            int i = pq3.begin()->second;
            pq3.erase(pq3.begin());
            lv[i] += 2;
        }
    }
    while (!pq3.empty() && rem >= pq3.begin()->first){
        rem -= pq3.begin()->first;
        ans2 += 2;
        int i = pq3.begin()->second;
        pq3.erase(pq3.begin());
        lv[i] += 2;
    }
    while (!pq2.empty() && rem >= pq2.begin()->first){
        rem -= pq2.begin()->first;
        ans2++;
        int i = pq2.begin()->second;
        pq2.erase(pq2.begin());
        if (lv[i] == 0) pq2.insert({c2[i], i});
        lv[i]++;
    }
    for (int i=0; i<N; i++){
        if (lv[i] == 0 && rem >= c1[i]){
            rem -= c1[i];
            ans2++;
        }
    }
    if (res <= K) ans = max(ans, ans2);
    return ans;
}

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