제출 #1255074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255074		VKhang	경주 (Race) (IOI11_race)	C++20	100 / 100	374 ms	33908 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,MOD=1e9+7;
#define ll long long
#define yes {cout<<"YES";return;}
#define no {cout<<"NO";return;}
#define srt(a,n) sort(a+1,a+n+1);
#define srt2(a,n,comp) sort(a+1,a+n+1,comp);
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define MAXN 1000005
int n,k;
vector <pair <int,int>> s[N];
int sz[N],high[N],dist[N],par[N];
bool visited[N];
int exist[MAXN];
int Save[MAXN];
int thutu = 0;
vector <pair <int,int>> tmp;
int res = 1e9;
int dfs(int i, int pre){
    sz[i] = 1;
    for (auto x: s[i]){
        if (x.fi == pre || visited[x.fi])
            continue;
        dist[x.fi] = dist[i] + x.se;
        sz[i] += dfs(x.fi,i);
    }
    return sz[i];
}
int Find_Centroid(int i, int pre, int Size){
    for (auto x: s[i]){
        if (x.fi == pre || visited[x.fi])
            continue;
        if (sz[x.fi] > Size/2)
            return Find_Centroid(x.fi,i,Size);
    }
    return i;
}
int dfs2(int i, int pre, int cnt, int d, int l){
    int ans = 1e9;
    if (d <= k && exist[k - d] == cnt){
        ans = min(ans, l + Save[k-d]);
    }
    if (d <= k){
        tmp.pb({d,l});
        for (auto x: s[i]){
            if (visited[x.fi] || x.fi == pre)
                continue;
            ans = min(ans, dfs2(x.fi,i,cnt,d + x.se,l + 1));
        }
    }
    return ans;
}
void Build_Centroid(int u,int p){
    int cnt = ++thutu;
    int Size = dfs(u,u);
    int centroid = Find_Centroid(u,u,Size);
    visited[centroid] = true;
    exist[0] = cnt;
    Save[0] = 0;
    for (auto x: s[centroid]){
        if (visited[x.fi])
            continue;
        tmp.clear();
       res = min(res, dfs2(x.fi,centroid,cnt,x.se,1));
        for (auto v: tmp){
            int i = v.fi;
            int j = v.se;
            if (exist[i] < cnt){
                exist[i] = cnt;
                Save[i] = j;
            }
            if (Save[i] > j)
                Save[i] = j;
        }
    }
    visited[centroid] = true;
    for (auto x: s[centroid]){
        if (visited[x.fi])
            continue;
        Build_Centroid(x.fi,u);
    }
}
int best_path(int _n, int _k, int h[][2], int L[])
{
    n = _n; k = _k;
    for (int i = 1;i < n;i++){
        int u,v,l;
        u = h[i - 1][0];
        v = h[i - 1][1];
        l = L[i - 1];
        s[u].pb({v,l});
        s[v].pb({u,l});
    }
    Build_Centroid(1,0);
    if (res == 1e9)
        return -1;
    else return res;
}

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