Submission #1233338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233338		Muhammad_Aneeq	Closing Time (IOI23_closing)	C++17	0 / 100	1096 ms	53556 KiB

closing

#include "closing.h"
#include <set>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<__int128,int>
#define ll __int128
int const N=2e5+10;
vector<pair<int,int>>nei[N]={};
__int128 dist[3][N]={};
__int128 dp[2*N]={};
int par[N]={};
bool wy[N]={};
vector<int>pth;
void bfs(int u,bool ind)
{
    dist[ind][u]=0;
    set<pair<__int128,int>>s;
    s.insert({0,u});
    if (ind==0)
        par[u]=-1;
    while (s.size())
    {
        __int128 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});
            }
        }
    }
}
vector<int>s;
int n;
void dfs(int u)
{
    for (auto [i,w1]:nei[u])
    {
        if (wy[i]||i==par[u]) continue;
        s.push_back(i);
        dfs(i);
    }
}
int fd(__int128 lef,int i,int j)
{
    s={};
    for (int k=0;k<pth.size();k++)
        dfs(pth[k]);
    for (int i=0;i<=2*n;i++)
        dp[i]=1e18+10;
    dp[0]=0;
    for (auto i:s)
    {
        for (int j=2*N;j>=1;j--)
        {
            dp[j]=min(dp[j],dp[j-1]+dist[0][i]);
            if (j>1)
                dp[j]=min(dp[j],dp[j-2]+dist[1][i]);
        }
    }
    int cur=0;
    for (int i=2*n;i>=0;i--)
    {
        if (dp[i]<=lef)
        {
            cur=i;
            break;
        }
    }
    return cur;
}
int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W)
{
    n=N;
    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<__int128>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<__int128>pre={0},pre1={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]);
    }
    __int128 cur=0;
    while (s.size())
    {
        __int128 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++)
        {
            __int128 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: 0 / 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