Submission #1275800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275800		nanaseyuzuki	Race (IOI11_race)	C++20	100 / 100	1324 ms	75292 KiB

race

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

const int mn = 1e6 + 5, bm = (1 << 20) + 1;
const int inf = 1e9;

int n, k, cnt = 0;
vector <pii> a[mn];
int st[mn], ft[mn], sz[mn], euler[mn], heavy[mn], d[mn], h[mn];
map <int, int> ans;

void txl(int u, int p){
    st[u] = ++cnt;
    euler[cnt] = u;
    sz[u] = 1;
    int max_val = 0, heavy_child = 0;
    for(auto i : a[u]){
        int v = i.fi, w = i.se;
        if(v == p) continue;
        d[v] = d[u] + 1;
        h[v] = h[u] + w;
        txl(v, u);
        sz[u] += sz[v];
        if(sz[v] > max_val){
            max_val = sz[v];
            heavy_child = v;
        }
    }
    heavy[u] = heavy_child;
    ft[u] = cnt;
}
int res = inf;

void dfs(int u, int p, bool keep){
    if(h[u] == k) res = min(res, d[u]);
    for(auto i : a[u]){
        int v = i.fi, w = i.se;
        if(v != p && v != heavy[u]) dfs(v, u, false);
    }
    if(heavy[u]) dfs(heavy[u], u, true);
    if(ans[h[u] + k] == 0) ans[h[u] + k] = inf;
    res = min(res, ans[h[u] + k] - d[u]);
    if(ans[h[u]] == 0) ans[h[u]] = inf;
    ans[h[u]] = min(ans[h[u]], d[u]);
    for(auto i : a[u]){
        int v = i.fi, w = i.se;
        if(v != p && v != heavy[u]){
            for(int i = st[v]; i <= ft[v]; i++){
                int depth = h[euler[i]];
                int left = 2 * h[u] + k - depth;
                if(ans[left] == 0) ans[left] = inf;
                res = min(res, d[euler[i]] + ans[left] - 2 * d[u]);
            }
            for(int i = st[v]; i <= ft[v]; i++){
                if(ans[h[euler[i]]] == 0) ans[h[euler[i]]] = inf;
                ans[h[euler[i]]] = min(ans[h[euler[i]]], d[euler[i]]);
            }
        }
    }
    if(!keep){
        for(int i = st[u]; i <= ft[u]; i++) ans[h[euler[i]]] = inf;
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0; i <= n - 2; i++){
        int u = H[i][0], v = H[i][1], w = L[i];
        ++u, ++v;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    txl(1, 0);
    dfs(1, 0, true);
    if (res > n - 1) res = -1;
    return res;
}

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