Submission #1248815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248815		Zbyszek99	Closing Time (IOI23_closing)	C++20	100 / 100	168 ms	39608 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<pll> graph[200001];
ll dist[200001][2];
ll cost1[200001];
ll cost2[200001];
int level[200001];
int T[200001];

void dfs(int v, int pop, ll d, int w)
{
    dist[v][w] = d;
    forall(it,graph[v])
    {
        if(it.ff != pop) dfs(it.ff,v,d+it.ss,w);
    }
}

int max_score(int n, int X, int Y, ll K, vi U, vi V, vi W)
{
    rep(i,n) graph[i] = {};
    rep(i,n-1)
    {
        graph[U[i]].pb({V[i],W[i]});
        graph[V[i]].pb({U[i],W[i]});
    }
    dfs(X,X,0,0);
    dfs(Y,Y,0,1);
    rep(i,n)
    {
        level[i] = 0;
        cost1[i] = min(dist[i][0],dist[i][1]);
        cost2[i] = max(dist[i][0],dist[i][1]) - cost1[i];
    }
    rep(i,n)
    {
        if(dist[i][0] + dist[i][1] == dist[Y][0]) T[i] = 0;
        else if(cost1[i] <= cost2[i]) T[i] = 1;
        else T[i] = 2;
    }
    int ans1 = 0;
    vl d;
    rep(i,n) d.pb(cost1[i]);
    ll used = 0;
    sort(all(d));
    forall(it,d)
    {
        used += it;
        if(used > K) break;
        ans1++;
    }
    int ans2 = 0;
    used = 0;
    rep(i,n)
    {
        if(T[i] == 0)
        {
            ans2++;
            used += cost1[i];
            level[i] = 1;
        }
    }
    if(used > K) return ans1;
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    priority_queue<pll,vector<pll>,greater<pll>> pq2;
    rep(i,n)
    {
        if(T[i] < 2)
        {
            if(level[i] == 0) pq.push({cost1[i],i});
            pq.push({cost2[i],i});
        }
        else
        {
            pq2.push({cost1[i]+cost2[i],i});
        }
    }
    while(!pq.empty() || !pq2.empty())
    {
     //   cerr << used << " " << ans2 << " used\n";
        if(siz(pq) == 0)
        {
            if(used + pq2.top().ff <= K)
            {
                pll t = pq2.top();
                pq2.pop();
                ans2+=2;
                used+=t.ff;
                level[t.ss] = 2;
                continue;
            }
            else break;
        }
        if(siz(pq2) == 0)
        {
            if(used + pq.top().ff <= K)
            {
                pll t = pq.top();
                pq.pop();
                ans2++;
                used+=t.ff;
                level[t.ss]++;
                continue;
            }
            else break;
        }
        ll c1 = pq.top().ff;
        pll xd = pq.top();
        pq.pop();
        if(siz(pq) != 0) c1 += pq.top().ff;
        else c1 += 1e18;
        pq.push(xd);
        ll c2 = pq2.top().ff;
       // cerr << c1 << " " << c2 << " " << ans2 << " " << used << " xd\n";
        if(used + min(c1,c2) > K)
        {
            if(used+pq.top().ff <= K)
            {
                ans2++;
                used += pq.top().ff;
                level[pq.top().ss]++;
                pq.pop();
                continue;
            }
            break;
        }
        if(c1 < c2)
        {
            ans2++;
            used += pq.top().ff;
            pll t = pq.top();
            pq.pop();
            level[t.ss]++;
        }
        else
        {
            ans2 += 2;
            used += c2;
            pll t = pq2.top();
            pq2.pop();
            level[t.ss] = 2;
        }
    }
    vl p;
    rep(i,n)
    {
        if(T[i] == 2 && level[i] == 0) p.pb(cost1[i]);
    }
    sort(all(p));
    forall(it,p)
    {
        used += it;
        if(used > K) break;
        ans2++;
    }
    return max(ans1,ans2);
}

• 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