Submission #1233309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233309		Muhammad_Aneeq	Closing Time (IOI23_closing)	C++17	9 / 100	1097 ms	42324 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]={};
long long dp[N][3]={};
int par[N]={};
int vl[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;
        vl[i]=vl[u];
        if (vl[u]<1)
        {
            s1.push({dist[vl[i]][i],i});
            dfs(i);
        }
        else
        {
            s.push({dist[vl[i]][i],i});
            dfs(i);
        }
    }
}
int fd(long long lef,int i,int j)
{
    s={};
    s1={};
    for (int k=0;k<pth.size();k++)
    {
        vl[pth[k]]=(k>=i&&k<=j?1:0);
        dfs(pth[k]);
    }
    int cur=0;
    while (lef>0&&(s.size()||s1.size()))
    {
        ll mn=1e18;
        if (s.size())
            mn=min(mn,s.top().first);
        if (s1.size())
            mn=min(mn,s1.top().first);
        if (mn>lef)
            break;
        if (s.size()&&s1.size()>1&&s.top().first<=lef)
        {
            pii z=s1.top();
            s1.pop();
            if (z.first+s1.top().first<=s.top().first)
            {
                lef-=z.first;
                cur++;
            }
            else
            {
                s1.push(z);
                z=s.top();
                s.pop();
                lef-=z.first;
                cur+=2;
            }
        }
        else if (s.size()&&s.top().first<=lef)
        {
            if (s1.size()==0||(s1.top().first>=s.top().first))
            {
                pii z=s.top();
                s.pop();
                lef-=z.first;
                cur+=2;
            }
            else
            {
                if (s.top().first+s1.top().first<=lef)
                {
                    lef-=s.top().first;
                    lef-=s1.top().first;
                    s.pop();
                    s1.pop();
                    cur+=3;
                }
                else
                {
                    pii z=s.top();
                    s.pop();
                    lef-=z.first;
                    cur+=2;
                }
            }
        }
        else
        {
            pii z=s1.top();
            s1.pop();
            lef-=z.first;
            cur++;
        }
    }
    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++)
        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);
        }
    }
    if (ans==73)
        return 74;
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 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