Submission #990661

#	Time	Username	Problem	Language	Result	Execution time	Memory
990661		aaaaaarroz	Closing Time (IOI23_closing)	C++17	100 / 100	151 ms	56560 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const int c=200005;
vector<pair<int, long long> > sz[c];
vector<pair<int, long long> > sor;
long long n, dist[c][2], bal, jobb, len, pref[2*c], inf=1e18;
bool ut[c];
void dfs(int a, int el, long long tav, int id) {
    dist[a][id]=tav;
    for (auto p:sz[a]) {
        int x=p.first;
        long long y=tav+p.second;
        if (x!=el) {
            dfs(x, a, y, id);
        }
    }
}
bool dfs2(int a, int el, long long tav) {
    if (a==jobb) {
        sor.push_back({a, tav});
        ut[a]=1;
        return true;
    }
    for (auto p:sz[a]) {
        int x=p.first;
        long long y=tav+p.second;
        if (x!=el) {
            if (dfs2(x, a, y)) {
                sor.push_back({a, tav});
                ut[a]=1;
                return true;
            }
        }
    }
    return false;
}
long long calc(long long ert) {
    if (ert<0) {
        return -inf;
    }
    int lo=0, hi=2*n+1, mid;
    while (hi-lo>1) {
        mid=(hi+lo)/2;
        if (pref[mid]<=ert) {
            lo=mid;
        } else {
            hi=mid;
        }
    }
    return lo;
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;
    for (int i=0; i<n-1; i++) {
        int a=U[i], b=V[i], c=W[i];
        sz[a].push_back({b, c});
        sz[b].push_back({a, c});
    }
    bal=X, jobb=Y;
    dfs(bal, -1, 0, 0), dfs(jobb, -1, 0, 1);
    len=dist[jobb][0];
    long long spec=0, maxi=0;
    if (true) {
        vector<long long> p;
        for (int i=0; i<n; i++) {
            p.push_back(dist[i][0]);
            p.push_back(dist[i][1]);
        }
        sort(p.begin(), p.end());
        long long sum=0, cnt=0;
        for (auto x:p) {
            if (sum+x<=K) {
                sum+=x;
                cnt++;
            }
        }
        spec=cnt;
    }
    bool s=dfs2(bal, -1, 0);
    reverse(sor.begin(), sor.end());
    long long si=sor.size(), sum=0, cnt=0, kezd=0, veg=si-1;
    while (kezd<=veg) {
        if (sor[kezd].second<=len-sor[veg].second) {
            cnt++;
            sum+=sor[kezd].second;
            kezd++;
        } else {
            cnt++;
            sum+=len-sor[veg].second;
            veg--;
        }
    }
    vector<long long> add;
    for (int i=kezd; i<si; i++) {
        add.push_back(2*sor[i].second-len);
    }
    for (int i=0; i<=veg; i++) {
        add.push_back(len-2*sor[i].second);
    }
    for (int i=1; i<=2*n; i++) {
        pref[i]=inf;
    }
    vector<pair<long long, long long> > dupla;
    vector<long long> prefmax, sufmin;
    for (int i=0; i<n; i++) {
        if (ut[i]) {
            continue;
        }
        long long a=dist[i][0], b=dist[i][1];
        if (a>b) {
            swap(a, b);
        }
        if (2*a<=b) {
            add.push_back(a);
            add.push_back(b-a);
        } else {
            dupla.push_back({b, a});
        }
    }
    sort(add.begin(), add.end());
    assert(add[0]>=0);
    for (int i=0; i<add.size(); i++) {
        pref[i+1]=pref[i]+add[i];
    }
    if (dupla.size()>0) {
        sort(dupla.begin(), dupla.end());
        int ds=dupla.size();
        prefmax.resize(ds), sufmin.resize(ds);
        prefmax[0]=dupla[0].first-dupla[0].second;
        for (int i=1; i<ds; i++) {
            prefmax[i]=max(prefmax[i-1], dupla[i].first-dupla[i].second);
        }
        sufmin[ds-1]=dupla[ds-1].second;
        for (int i=ds-2; i>=0; i--) {
            sufmin[i]=min(sufmin[i+1], dupla[i].second);
        }
        maxi=max(maxi, cnt+calc(K-sum));
        maxi=max(maxi, cnt+1+calc(K-sum-sufmin[0]));
        for (int i=0; i<ds; i++) {
            sum+=dupla[i].first;
            maxi=max(maxi, cnt+2*i+1+calc(K-sum+prefmax[i]));
            maxi=max(maxi, cnt+2*i+2+calc(K-sum));
            if (i+1<ds) {
                maxi=max(maxi, cnt+2*i+3+calc(K-sum-sufmin[i+1]));
            }
        }
    }
    maxi=max(maxi, cnt+calc(K-sum));
    for (int i=0; i<=n; i++) {
        sz[i].clear();
        ut[i]=0;
    }
    sor.clear();
    len=0;
    return max(maxi, spec);
}

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:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i=0; i<add.size(); i++) {
      |                   ~^~~~~~~~~~~
closing.cpp:80:10: warning: unused variable 's' [-Wunused-variable]
   80 |     bool s=dfs2(bal, -1, 0);
      |          ^

• 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