Submission #1065290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065290		LittleOrange	Closing Time (IOI23_closing)	C++17	29 / 100	1048 ms	34644 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);
    ll is_line = 1;
    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]});
        if(U[i]!=i||V[i]!=i+1) is_line = 0;
    }
    if (is_line){
        auto &w = W;
        vector<ll> pw(n,0);
        for(ll i = 0;i<n-1;i++) pw[i+1] = pw[i]+w[i];
        vector<ll> v,cc(n,0);
        for(ll i = 0;i<x;i++){
            v.push_back(cc[i] = pw[x]-pw[i]);
        }
        for(ll i = y+1;i<n;i++){
            v.push_back(cc[i] = pw[i]-pw[y]);
        }
        vector<ll> pc(n+1,0);
        for(ll i = 0;i<n;i++) pc[i+1] = cc[i]+pc[i];
        sort(v.begin(),v.end());
        for(ll i = 1;i<v.size();i++) v[i]+=v[i-1];
        ll ans = 0;
        vector<ll> h(n,0),h1(n,0);
        ll lv1 = 0;
        for(ll i = x;i<n;i++){
            h[i] = pw[i]-pw[x];
            h1 = h;
            lv1 += h[i];
            ll lv2 = lv1;
            for(ll j = y;j>=0;j--){
                h1[j] = max(h[j],pw[y]-pw[j]);
                lv2 += max(pw[y]-pw[j]-h[j],0ll);
                if (lv2>k) break;
                ll g = 2+i-x+y-j;
                vector<ll> v;
                for(ll p = 0;p<x;p++){
                    v.push_back(max(0ll,pw[x]-pw[p]-h1[p]));
                }
                for(ll p = y+1;p<n;p++){
                    v.push_back(max(0ll,pw[p]-pw[y]-h1[p]));
                }
                sort(v.begin(),v.end());
                ll cur = lv2;
                for(ll i : v) if(cur+i<=k){
                    cur += i;
                    g++;
                }
                ans = max(ans,g);
            }
        }
        return ans;
    }
    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:38:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(ll i = 1;i<v.size();i++) v[i]+=v[i-1];
      |                      ~^~~~~~~~~
closing.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |         ll m = l+r+1>>1;
      |                ~~~^~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 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