Submission #841773

#	Time	Username	Problem	Language	Result	Execution time	Memory
841773		Lyestria	Closing Time (IOI23_closing)	C++17	35 / 100	93 ms	40688 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;
}

int 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]});
    }
    fpath(x,x,y);
    reverse(all(path));
    for(int a : path)inpath[a]=1;
    ll D = dis[y];
    struct Choice {
        ll d;
        int a;
        bool sec;
        bool operator<(const Choice &o) const {return d>o.d;}
    };
    vector<ll> costt;
    priority_queue<Choice> pq;
    for(auto [a,w] : g[x]) if(!inpath[a]) {
        pq.push({w,a,0});
    }
    for(auto [a,w] : g[y]) if(!inpath[a]) {
        pq.push({w,a,0});
    }

    while(pq.size()) {
        auto [d,a,sec] = pq.top();
        pq.pop();
        vis[a]=1;
        costt.push_back(d);
        if(sec)continue;
        pq.push({D,a,1});
        for(auto [b,w] : g[a])if(!inpath[b]&&!vis[b]){
            pq.push({d+w,b,0});
        }
    }

    vector<ll> costl;

    pq.push({0,x,0});
    pq.push({0,y,0});
    while(pq.size()) {
        auto [d,a,s] = pq.top();
        pq.pop();
        if(vis[a])continue;
        vis[a]=1;
        costl.push_back(d);
        for(auto [b,w] : g[a]) if(inpath[b]&&!vis[b]){
            pq.push({d+w,b,0});
        } 
    }
    // cerr << costl.size() << endl;
    vector<ll> cost2;
    for(int a : path) {
        cost2.push_back(abs(dis[a]-(D-dis[a])));
    }
    sort(all(cost2));
    for(ll x : cost2) costl.push_back(x);

    int ans = 0;
    ll sum = 0;
    for(int i=0;i<costl.size();i++)sum+=costl[i];
    // cerr << costl.size() << " " << costt.size() << endl;
    for(int i=-1,j=(int)costl.size()-1;i<(int)costt.size();i++){
        while(sum>k&&j>=0){
            sum-=costl[j];
            j--;
            // cerr << sum << j << endl;
        }
        // cerr << "ij " << i << " " << j << endl; 
        if(sum<=k)ans=max(ans,(i+1)+(j+1));
        if(i==(int)costt.size()-1)break;
        sum+=costt[i+1];
    }
    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:37:55: 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++){
      |                 ~^~~~~~~~~
closing.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<costl.size();i++)sum+=costl[i];
      |                 ~^~~~~~~~~~~~~

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