Submission #1148766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148766		son2008	Race (IOI11_race)	C++20	100 / 100	601 ms	52316 KiB

race

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e6+5;
const int mod=1e9+7;
int n,root,sz[maxn],h[maxn],q,par[maxn],ans=2e9,mn[maxn],mx_h,k;
bool is_centroid[maxn];
vector<ii>a[maxn];
void dfs(int u,int cha)
{
    sz[u]=1;
    for(ii v:a[u])
    {
        if(v.fi==cha||is_centroid[v.fi])continue;
        dfs(v.fi,u);
        sz[u]+=sz[v.fi];
    }
}
int find_centroid(int u,int tree_sz,int cha)
{
    for(ii v:a[u])
        if(v.fi!=cha&&!is_centroid[v.fi]&&sz[v.fi]>tree_sz/2) return find_centroid(v.fi,tree_sz,u);
    return u;
}
void get(int u,int cha,int h,int w,int t)
{
    if(w>k)return;
    if(t==0)
    ans=min(ans,mn[k-w]+h);
    else mn[w]=min(mn[w],h);
    mx_h=max(mx_h,w);
    for(ii v:a[u])
    {
        if(v.fi==cha||is_centroid[v.fi])continue;
        get(v.fi,u,h+1,w+v.se,t);
    }
}
void build_centroid(int u,int pre_centroid)
{
    dfs(u,-1);
    int centroid=find_centroid(u,sz[u],-1);
    if(root==0)root=centroid;
    mx_h=0;
    is_centroid[centroid]=true;
    for(ii v:a[centroid])
    {
        if(!is_centroid[v.fi])
        {
            get(v.fi,centroid,1,v.se,0);
            get(v.fi,centroid,1,v.se,1);
        }
    }
    for(int i=1;i<=mx_h;i++)mn[i]=2e9;
    for(ii v:a[centroid])
    {
        if(!is_centroid[v.fi])build_centroid(v.fi,centroid);
    }
}
int best_path(int N,int K,int H[][2],int w[])
{
    k=K,n=N;
    for(int i=0;i<n-1;i++)
    {
        a[H[i][0]+1].push_back({H[i][1]+1,w[i]});
        a[H[i][1]+1].push_back({H[i][0]+1,w[i]});
    }
    for(int i=0;i<=k;i++)mn[i]=2e9;
    ans=2e9;
    mn[0]=0;
    build_centroid(1,-1);
    if(ans>=2e9)return -1;
    else return ans;
}

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