Submission #1065167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065167		LittleOrange	Closing Time (IOI23_closing)	C++17	8 / 100	151 ms	34640 KiB

closing

#include "closing.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 2e18;
struct line{
    ll i,w;
};
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    ll n = N;
    ll x = X;
    ll y = Y;
    ll k = K;
    vector<vector<line>> con(n);
    for(ll i = 0;i<n-1;i++){
        con[U[i]].push_back({V[i],W[i]});
        con[V[i]].push_back({U[i],W[i]});
    }
    vector<ll> dis1(n,big),dis2(n,big);
    {
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll v){
            if(dis1[i]>v){
                dis1[i] = v;
                for(auto [j,w] : con[i]){
                    dfs(j,v+w);
                }
            }
        };
        dfs(x,0);
    }
    {
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll v){
            if(dis2[i]>v){
                dis2[i] = v;
                for(auto [j,w] : con[i]){
                    dfs(j,v+w);
                }
            }
        };
        dfs(y,0);
    }
    ll l = 0, r = big;
    while(l<r){
        ll m = l+r+1>>1;
        ll sm = 0;
        for(ll i = 0;i<n;i++){
            ll mi = min(dis1[i],dis2[i]);
            ll mx = max(dis1[i],dis2[i]);
            if(m>=mx) sm+=mx;
            else if(m>=mi) sm+=mi;
        }
        if(sm>k) r = m-1;
        else l = m;
    }
    ll cur = 0, ans = 0;
    vector<ll> v;
    for(ll i = 0;i<n;i++){
        ll mi = min(dis1[i],dis2[i]);
        ll mx = max(dis1[i],dis2[i]);
        if (mx<=l){
            cur += mx;
            ans += 2;
        }else if (mi<=l){
            cur += mi;
            ans += 1;
            if (mx==l+1){
                v.push_back(mx-mi);
            }
        }else if(mi==l+1){
            v.push_back(mi);
        }
    }
    sort(v.begin(),v.end());
    for(ll i : v){
        if(cur+i<=k){
            ans += 1;
            cur += i;
        }
    }
    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:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         ll m = l+r+1>>1;
      |                ~~~^~

• 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