Submission #886940

#	Time	Username	Problem	Language	Result	Execution time	Memory
886940		fryingduc	Race (IOI11_race)	C++17	100 / 100	319 ms	140732 KiB

race

#include "bits/stdc++.h"
using namespace std;

//#define int long long

const int maxn = 1e6+5;
const int inf = 1e9+10;
int n, l;
int sz[maxn], tin[maxn], tout[maxn], timer;
long long h[maxn];
int dak[maxn], depth[maxn], et[maxn];
vector<pair<int, int>> g[maxn];
multiset<int> mn[maxn];
vector<long long> vec;
int ans = inf;
void pre_dfs(int u, int prev){
    sz[u] = 1;
    tin[u] = ++timer;
    et[timer] = u;
    for(auto e:g[u]){
        int v = e.first, w = e.second;
        if(v == prev) continue;
        depth[v] = depth[u] + 1;
        h[v] = h[u] + w;
        pre_dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = timer;
}
void dfs(int u, int prev, bool keep){
    int bigchild = -1;
    for(auto e:g[u]){
        int v = e.first;
        if(v == prev) continue;
        if(bigchild == -1 || sz[bigchild] < sz[v]) bigchild = v;        
    }
    for(auto e:g[u]){
        int v = e.first;
        if(v == prev || v == bigchild) continue;
        dfs(v, u, 0);
    }
    if(bigchild != -1) dfs(bigchild, u, 1);
    
    int mim = lower_bound(vec.begin(), vec.end(), 1LL * h[u] + l) - vec.begin();
    if(mim < (int)vec.size() and vec[mim] == h[u] + l){
        if(mn[mim].size()) ans = min(ans, *mn[mim].begin() - depth[u]);
    }
    mn[dak[u]].insert(depth[u]);
    
    for(auto e:g[u]){
        int v = e.first;
        if(v == prev || v == bigchild) continue;
        
        for(int i = tin[v]; i <= tout[v]; ++i){
            long long val = 2LL * h[u] + l - h[et[i]];
            int pos = lower_bound(vec.begin(), vec.end(), val) - vec.begin();
            if(pos < (int)vec.size() and vec[pos] == val){
                if(mn[pos].size()) ans = min(ans, *mn[pos].begin() + depth[et[i]] - 2 * depth[u]);
            }
        }
        
        for(int i = tin[v]; i <= tout[v]; ++i){
            mn[dak[et[i]]].insert(depth[et[i]]);
        }
    }
    
    if(keep) return;
    for(int i = tin[u]; i <= tout[u]; ++i){
        mn[dak[et[i]]].erase(depth[et[i]]);
    }
    
}
int best_path(int _n, int _k, int edges[][2], int weights[]){
    n = _n, l = _k;
    for(int i = 0; i < n - 1; ++i){
        int u = edges[i][0], v = edges[i][1], w = weights[i]; 
        ++u, ++v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    pre_dfs(1, 0);
    
    for(int i = 1; i <= n; ++i){
        vec.push_back(h[i]);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i = 1; i <= n; ++i){
        dak[i] = lower_bound(vec.begin(), vec.end(), h[i]) - vec.begin();
    }
    
    dfs(1, 0, 1);
    return (ans > n ? -1 : ans);
}

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