Submission #843135

#	Time	Username	Problem	Language	Result	Execution time	Memory
843135		Lyestria	Closing Time (IOI23_closing)	C++17	100 / 100	259 ms	60172 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using ll = long long;

const int maxn = 5e5 + 10;
const ll inf = 1e18 + 100;

vector<pair<int,ll>> g[maxn];
vector<int> path;
bool inpath[maxn];
ll dis[maxn];
bool fpath(int x,int p,int t) {
    if(x==t){
        path.push_back(x);
        return true;
    }
    for(auto [y,w] : g[x]) if(y!=p) {
        dis[y] = dis[x] + w;
        if(fpath(y,x,t)){
            path.push_back(x);
            return true;
        }
    }
    return false;
}

bool vis[maxn];
int max_score(int n, int x, int y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // cerr << endl;
    for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
    path.clear();
    for(int i=0;i<U.size();i++){
        g[U[i]].push_back({V[i],W[i]});
        g[V[i]].push_back({U[i],W[i]});
    }

    // no overlap
    int ans1 = [&](){
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        pq.push({0,x});
        pq.push({0,y});
        ll sum = 0;
        int ans = 0;
        while(pq.size()){
            auto [d,a] = pq.top();
            pq.pop();
            // cerr << ans << " " << sum << " " << k << " " << d << " " << vis[a] << endl;
            if(vis[a])continue;
            vis[a]=1;
            if(sum+d>k){
                return ans;
            }
            sum+=d;
            ans++;
            // cerr << ans << endl;
            for(auto [b,w] : g[a]) {
                pq.push({d+w,b});
            }
        }
        return ans;
    }();

    // overlap (start with path)
    int ans2 = [&](){
        for(int i=0;i<n;i++)vis[i]=0;
        fpath(x,x,y);
        reverse(all(path));
        for(int a : path)inpath[a]=1;
        int ans = 0;
        ll sum = 0;
        const ll D = dis[y];

        for(int a : path) {
            ans++;
            sum += min(dis[a],D-dis[a]);
        }
        if(sum > k) return 0;

        struct State {
            ll c1, c2;
            int a;
            ll pc1;
            ll eval() const {return min(c1*2,c2); }
            bool operator<(const State &o) const {return eval() > o.eval(); }
        };

        priority_queue<State>pq;
        for(int a : path) {
            pq.push({max(dis[a],D-dis[a])-min(dis[a],D-dis[a]), inf, a});
            for(auto [b,w] : g[a]) if(!inpath[b]) {
                pq.push({min(dis[a],D-dis[a])+w, max(dis[a],D-dis[a])+w, b});
            }
            vis[a]=1;
        }
        multiset<ll> sing;
        while(pq.size()){
            auto [c1,c2,a,pc1] = pq.top();
            // cerr << c1 << " " << c2 << " " <<a << endl;
            pq.pop();
            vis[a]=1;
            if(sum+c1<=k){
                ans++;
                sum+=c1;
            }
            else {
                // cerr << "poor" << endl;
                if(sing.size()==0)continue;
                auto it = --sing.end();
                // cerr << *it << endl;
                if(sum-*it+c2<=k){
                    return ans+1;
                }
                continue;
            }

            sing.insert(c1);
            if(c2>=inf){
                if(!inpath[a]){
                    sing.erase(sing.find(pc1));
                }
                continue;
            }
            pq.push({c2-c1,inf,a,c1});
            for(auto [b,w] : g[a]) if(!vis[b]) {
                pq.push({c1+w,c2+w,b});
            }
        }
        // cerr << "here " << k-sum << endl;
        return ans;
    }();

    return max(ans1,ans2);
}

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:37:62: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |     for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
      |                                                        ~~~~~~^~
closing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~

• 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