Submission #1016875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016875		Andrey	Closing Time (IOI23_closing)	C++17	100 / 100	202 ms	66176 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

long long n,x,y,k;
vector<pair<long long,long long>> haha[200001];
vector<long long> bruh(200001);
vector<long long> wow(200001);
vector<pair<long long,long long>> idk(0);

void dfs(long long a, long long t, long long d, bool yeah) {
    if(yeah) {
        bruh[a] = d;
    }
    else {
        wow[a] = d;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+v.second,yeah);
        }
    }
}

bool dude(long long a, long long t) {
    if(a == y) {
        if(bruh[a] < wow[a]) {
            k-=bruh[a];
            wow[a]-=bruh[a];
            bruh[a] = 0;
        }
        else {
            k-=wow[a];
            bruh[a]-=wow[a];
            wow[a] = 0;
        }
        return true;
    }
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            if(dude(v.first,a)) {
                if(bruh[a] < wow[a]) {
                    k-=bruh[a];
                    wow[a]-=bruh[a];
                    bruh[a] = 0;
                }
                else {
                    k-=wow[a];
                    bruh[a]-=wow[a];
                    wow[a] = 0;
                }
                return true;
            }
        }
    }
    return false;
}

long long solve() {
    long long sb = 0;
    vector<int> ans(n+1,-1);
    priority_queue<pair<long long,pair<long long,long long>>> no;
    priority_queue<pair<long long,pair<long long,long long>>> rem;
    priority_queue<pair<long long,long long>> dv;
    no.push({-LLONG_MAX/3,{n,-1}});
    rem.push({-LLONG_MAX/3,{n,-1}});
    dv.push({-LLONG_MAX/3,-1});
    for(int i = 0; i < n; i++) {
        ans[i] = 0;
        no.push({-idk[i].first,{i,0}});
        dv.push({-idk[i].second-idk[i].first,i});
    }
    for(int i = 0; i < 2*n; i++) {
        while(ans[no.top().second.first] != no.top().second.second) {
            no.pop();
        }
        while(ans[rem.top().second.first] != rem.top().second.second) {
            rem.pop();
        }
        while(dv.top().second != -1 && ans[dv.top().second] != 0) {
            dv.pop();
        }
        if(-dv.top().first-rem.top().first < -no.top().first) {
            long long p1 = rem.top().second.first,p2 = dv.top().second,c = -dv.top().first-rem.top().first;
            ans[p1]--;
            ans[p2]+=2;
            sb+=c;
            rem.push({idk[p2].second,{p2,2}});
            if(ans[p1] == 1) {
                rem.push({idk[p1].first,{p1,1}});
                no.push({-idk[p1].second,{p1,1}});
            }
            else {
                no.push({-idk[p1].first,{p1,0}});
                dv.push({-idk[p1].second-idk[p1].first,p1});
            }
        }
        else {
            ans[no.top().second.first]++;
            long long c,p = no.top().second.first;
            if(no.top().second.second == 1) {
                c = idk[p].second;
            }
            else {
                c = idk[p].first;
                no.push({-idk[p].second,{p,ans[p]}});
            }
            sb+=c;
            rem.push({c,{p,ans[p]}});
        }
        if(sb > k) {
            return i;
        }
    }
    return 2*n;
}

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;
    x = X;
    y = Y;
    k = K;
    for(int i = 0; i < n; i++) {
        haha[i].clear();
    }
    for(long long i = 0; i < n-1; i++) {
        haha[U[i]].push_back({V[i],W[i]});
        haha[V[i]].push_back({U[i],W[i]});
    }
    long long ans = 0;
    dfs(x,-1,0,true);
    dfs(y,-1,0,false);
    vector<long long> wut(n);
    for(long long i = 0; i < n; i++) {
        wut[i] = min(bruh[i],wow[i]);
    }
    sort(wut.begin(),wut.end());
    long long sb = 0;
    for(long long i = 0; i < wut.size(); i++) {
        sb+=wut[i];
        if(sb > k) {
            break;
        }
        ans++;
    }
    dude(x,-1);
    if(k < 0) {
        return ans;
    }
    idk.clear();
    for(int i = 0; i < n; i++) {
        idk.push_back({min(bruh[i],wow[i]),max(bruh[i],wow[i])-min(bruh[i],wow[i])});
    }
    return max(solve(),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:140:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(long long i = 0; i < wut.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