제출 #1162584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162584		ASGA_RedSea	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"


#pragma GCC optimize("Ofast")


#include<bits/stdc++.h>


using namespace std;
using ll=long long;


#include "race.h"

int n,k,ans=1e9,inf=1e9;
vector<vector<array<ll,2>>>a;
vector<int>sz,vis,d,dd;

int mn,mx,mmn,mmx,tot;
void gsz(int i,int p){
    sz[i]=1;
    for(auto&[j,w]:a[i]){
        if(!vis[j]&&j!=p){gsz(j,i);sz[i]+=sz[j];}
    }
}
int gc(int i,int p){
    for(auto&[j,w]:a[i]){
        if(!vis[j]&&j!=p&&sz[j]*2>tot)return gc(j,i);
    }
    return i;
}

void calc1(int i,int p,int dis,int dpt){
    d[dis]=min(d[dis],dpt);

    mn=min(mn,dis);
    mx=max(mx,dis);

    for(auto&[j,w]:a[i]){
        if(!vis[j]&&j!=p&&dis+w<=k)calc1(j,i,dis+w,dpt+1);
    }
}

void calc(int i){
    gsz(i,-1);tot=sz[i];
    int c=gc(i,-1);
    vis[c]=1;



    mmn=mmx=0;
    d[0]=dd[0]=0;

    for(auto&[j,w]:a[c]){
        if(vis[j]||w>k)continue;

        mn=mx=0;
        calc1(j,c,w,1);


        for(int l=mn;l<=mx;l++){

            ans=min(ans,dd[k-l]+d[l]);
        }

        for(int l=mn;l<=mx;l++){dd[l]=min(dd[l],d[l]);d[l]=inf;}
    }

    ans=min(ans,dd[k]);

    for(int l=mmx;l<=mmx;l++)dd[k]=inf;

    for(auto&[j,w]:a[c]){
        if(!vis[j])calc(j);
    }
}

int best_path(int N,int K,int H[][2],int L[]){
    n=N;k=K;a.resize(n);
    for(int i=0;i+1<n;i++){
        int u=H[i][0],v=H[i][1],w=L[i];
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    vis.assign(n,0);sz=vis;
    d.assign(k+1,inf);dd=d;
    calc(0);
    return (ans==inf?-1:ans);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57