제출 #797480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797480		Khizri	경주 (Race) (IOI11_race)	C++17	21 / 100	165 ms	162648 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=5e5+5;
ll n,k,ans,par[mxn],sum[mxn];
vector<pii>vt[mxn];
vector<int>dis[mxn];
void dfs1(int u,int p,int dep,int cnt){
    if(dep==k) ans=min(ans,(ll)cnt);
    for(pii v:vt[u]){
        if(p!=v.F){
            dfs1(v.F,u,dep+v.S,cnt+1);
        }
    }
}
void dfs(int u,int p){
    //cout<<u<<' '<<p<<endl;
    par[u]=p;
    int node=p;
    int cnt=1;
    while(node!=-1&&sum[u]-sum[node]<=k){
        dis[node][sum[u]-sum[node]]=min(dis[node][sum[u]-sum[node]],cnt);
        cnt++;
        node=par[node];
        //cout<<node<<endl;
    }
    multiset<int>st[105];
    st[0].insert(0);
    for(int i=1;i<=k+5;i++) st[i].insert(1e9);
    for(pii pp:vt[u]){
        int v=pp.F,len=pp.S;
        if(v==p) continue;
        sum[v]=sum[u]+len;
        dfs(v,u);
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k){
                st[dif].insert(dis[v][i]+1);
            }
        }
    }
    for(pii pp:vt[u]){
        int v=pp.F,len=pp.S;
        if(v==p) continue;
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k){
                st[dif].erase(st[dif].find(dis[v][i]+1));
            }
        }
        for(int i=0;i<=100;i++){
            int dif=len+i;
            if(dif<=k){
                int res=dis[v][i]+1;
                res+=*st[k-dif].begin();
                ans=min(ans,(ll)res);
            }
        }
        for(int i=0;i<=k;i++){
            int dif=len+i;
            if(dif<=k){
                st[dif].insert(dis[v][i]+1);
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for(int i=0;i<n-1;i++){
        int u=H[i][0]+1,v=H[i][1]+1;
        vt[u].pb({v,L[i]});
        vt[v].pb({u,L[i]});
        if(L[i]==k) return 1;
    }
    if(n<=1000){
        ans=1e9;
        for(int i=1;i<=n;i++){
            dfs1(i,-1,0,0);
        }
        if(ans==1e9) return -1;
        return ans;
    }
    for(int i=1;i<=n;i++){
        dis[i].pb(0);
        for(int j=1;j<=k;j++){
            dis[i].pb(1e9);
        }
    }
    ans=1e9;
    dfs(1,-1);
    if(ans==1e9) return -1;
    return ans;
}
/*
g++ race.cpp grader.cpp ; .\a.exe
4 3 
0 1 1 
1 2 2 
1 3 4

11 12
0 1 3
0 2 4
2 3 5
3 4 4 
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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