Submission #1233324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233324		Muhammad_Aneeq	Closing Time (IOI23_closing)	C++17	21 / 100	1096 ms	42232 KiB

closing

#include "closing.h"
#include <set>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<long long,int>
#define ll long long
int const N=2e5+10;
vector<pair<int,int>>nei[N]={};
long long dist[3][N]={};
int par[N]={};
bool wy[N]={};
vector<int>pth;
void bfs(int u,bool ind)
{
    dist[ind][u]=0;
    set<pair<long long,int>>s;
    s.insert({0,u});
    if (ind==0)
        par[u]=-1;
    while (s.size())
    {
        long long u=(*begin(s)).second,w=(*begin(s)).first;
        s.erase(*begin(s));
        if (dist[ind][u]!=w) continue;
        for (auto [i,w1]:nei[u])
        {
            if (dist[ind][i]>w+w1)
            {
                if (ind==0)
                    par[i]=u;
                dist[ind][i]=w+w1;
                s.insert({dist[ind][i],i});
            }
        }
    }
}
priority_queue<pair<long long,int>,vector<pair<long long ,int>>,greater<pair<long long,int>>>s,s1;
void dfs(int u)
{
    for (auto [i,w1]:nei[u])
    {
        if (wy[i]||i==par[u]) continue;
        s.push({dist[0][i],i});
        dfs(i);
    }
}
int fd(long long lef,int i,int j)
{
    s={};
    for (int k=0;k<pth.size();k++)
        dfs(pth[k]);
    // for (auto i:s)
    //     cout<<i.first<<' ';
    // cout<<endl;
    // for (auto i:s1)
    //     cout<<i.first<<' ';
    // cout<<endl;
    int cur=0;
    while (lef>0&&s.size())
    {
        pii z=s.top();
        s.pop();
        if (z.first>lef)
            break;
        lef-=z.first;
        cur++;
        if (z.second>0)
            s.push({dist[1][z.second]-dist[0][z.second],-z.second});
    }
    return cur;
}
int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W)
{
    pth={};
    for (int i=0;i<N;i++)
    {
        wy[i]=0;
        nei[i]={};
    }
    for (int i=0;i<U.size();i++)
    {
        nei[U[i]].push_back({V[i],W[i]});
        nei[V[i]].push_back({U[i],W[i]});
    }
    for (int i=0;i<N;i++)
        dist[0][i]=dist[1][i]=1e18;
    bfs(X,0);
    bfs(Y,1);
    int ans=0;
    multiset<long long>s;
    for (int i=0;i<N;i++)
    {
        s.insert(dist[0][i]);
        s.insert(dist[1][i]);
        if (dist[0][i]>dist[1][i])
            swap(dist[0][i],dist[1][i]);
    }
    int f=Y;
    while (f!=-1)
    {
        pth.push_back(f);
        f=par[f];
    }
    for (auto i:pth)
        wy[i]=1;
    reverse(begin(pth),end(pth));
    vector<long long>pre={0},pre1={0},pre2={0};
    int sz=pth.size();
    for (auto i:pth)
    {
        pre.push_back(pre.back()+dist[1][i]);
        pre1.push_back(pre1.back()+dist[0][i]);
    }
    long long cur=0;
    while (s.size())
    {
        long long w=(*begin(s));
        if (cur+w>k)
            break;
        ans++;
        cur+=w;
        s.erase(begin(s));
    }
    s={};
    for (int i=0;i<sz;i++)
    {
        for (int j=i;j<sz;j++)
        {
            long long init=pre[j+1]-pre[i];
            init+=pre1[i];
            if (j+1<=sz)
                init+=(pre1[sz]-pre1[j+1]);
            if (init>k) continue;
            int g=fd(k-init,i,j);
            int tr=(j-i+1)+sz+g;
            ans=max(ans,tr);
        }
    }
    return ans;
}

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