Submission #1212232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212232		Aviansh	Closing Time (IOI23_closing)	C++20	43 / 100	97 ms	36928 KiB

closing

#include "closing.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

void dfs(int st, vector<array<int,2>>g[], int p, long long dist[], long long d){
    dist[st]=d;
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,st,dist,d+e[1]);
    }
}

int max_score(int n, int x, int y, long long k, vector<int> u, vector<int> v, vector<int> w) {
    vector<array<int,2>>g[n];
    int m = u.size();
    for(int i = 0;i<m;i++){
        g[u[i]].push_back({v[i],w[i]});
        g[v[i]].push_back({u[i],w[i]});
    }
    long long distx[n], disty[n];
    dfs(x,g,-1,distx,0);
    dfs(y,g,-1,disty,0);
    long long cost1[n],cost2[n];
    for(int i = 0;i<n;i++){
        cost1[i]=min(distx[i],disty[i]);
        cost2[i]=max(distx[i],disty[i])-cost1[i];
    }
    int ans1 = 0;
    //only till level 1.
    priority_queue<long long,vector<long long>,greater<long long>>pq;
    for(int i = 0;i<n;i++){
        pq.push(cost1[i]);
    }
    long long curk = 0;
    while(curk<=k&&pq.size()){
        long long a = pq.top();
        pq.pop();
        if(curk+a>k)
            break;
        ans1++;
        curk+=a;
    }
    assert(curk<=k);
    curk=0;
    int ans2 = 0;
    //now both levels, after doing all in between.
    bool vis[n];
    fill(vis,vis+n,0);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq2;
    for(int i = 0;i<n;i++){
        if(i<x){
            pq2.push({cost1[i],i});
        }
        if(x<=i&&i<=y){
            pq2.push({cost2[i],i});
            curk+=cost1[i];
            vis[i]=1;
            ans2++;
        }
        if(y<i){
            pq2.push({cost1[i],i});
        }
    }
    if(curk>k){
        return ans1;
    }
    while(curk<=k&&pq2.size()){
        pair<long long,int>p = pq2.top();
        pq2.pop();
        long long a = p.first;
        int i = p.second;
        if(curk+a>k)
            break;
        ans2++;
        curk+=a;
        if(vis[i])
            continue;
        vis[i]=1;
        pq2.push({cost2[i],i});
    }
    assert(curk<=k);
    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: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17