Submission #1281857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281857		quan606303	경주 (Race) (IOI11_race)	C++20	100 / 100	710 ms	39504 KiB

race

#include <bits/stdc++.h>
bool M1;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define memfull(a,b) memset(a,b,sizeof(a));
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const ll MOD=1e9+7;
const ll maxn=1e6+7;
ll sz[maxn];
bool is_deleted[maxn];
vector<pair<ll,ll> > adj[maxn];
ll n,k,cnt[maxn],ans=1e18;
void cal_sz(ll u,ll p)
{
    sz[u]=1;
    for (auto v:adj[u])
    {
        if (v.fi==p||is_deleted[v.fi])continue;
        cal_sz(v.fi,u);
        sz[u]+=sz[v.fi];
    }
}
ll find_centroid(ll u,ll p,ll N)
{
    for (auto v:adj[u])
    {
        if (v.fi!=p&&!is_deleted[v.fi]&&sz[v.fi]>N)return find_centroid(v.fi,u,N);
    }
    return u;
}
void cal(ll u,ll p,ll w,ll type,ll h)
{
    if (w>k)return ;
    if (type==1)ans=min(ans,cnt[k-w]+h);
    else if (type==0)cnt[w]=min(cnt[w],h);
    else if (type==-1)cnt[w]=1e18;
    for (auto v:adj[u])
    {
        if (v.fi==p||is_deleted[v.fi])continue;
        cal(v.fi,u,w+v.se,type,h+1);
    }
}
void centroid_decomposition(ll u)
{
    cal_sz(u,0);
    ll N=sz[u];
    ll root=find_centroid(u,0,N/2);
    is_deleted[root]=true;
    cnt[0]=0;
    for (auto v:adj[root])
    {
        if (!is_deleted[v.fi])
        {
            cal(v.fi,root,v.se,1,1);
            cal(v.fi,root,v.se,0,1);
        }
    }
    cnt[0]=1e18;
    for (auto v:adj[root])
    {
        if (!is_deleted[v.fi])
        {
            cal(v.fi,root,v.se,-1,1);
        }
    }
    for (auto v:adj[root])if (!is_deleted[v.fi])centroid_decomposition(v.fi);
}
int best_path(int N, int K, int H[][2], int L[]) {
	n = N, k = K;
	for (int i=0;i<n;i++){
		adj[H[i][0]+1].push_back({H[i][1]+1,L[i] });
		adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
	}
	for (int i=0;i<=k;i++)cnt[i]=1e18;
    centroid_decomposition(1);
    return (ans==1e18?-1:ans);
}

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