Submission #1052143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052143		JosephA	Race (IOI11_race)	C++17	9 / 100	121 ms	52076 KiB

race

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

#define pb push_back
#define SZ(x) (int)(x).size()
typedef long long ll;

struct E { int v; ll w; };

struct Tree{
    int n, l;
    vector<vector<int>>adj;
    vector<ll>depth, parent, subtree, tin, tout;
    vector<vector<int>>up;
    int timer;
    Tree(int n){
        this->n = n;
        adj.resize(n + 1);
        depth.resize(n + 1);
        parent.resize(n + 1);
        subtree.resize(n + 1);
        tin.resize(n + 1);
        tout.resize(n + 1);
        timer = 0;
        l = ceil(log2(n));
        up.resize(n + 1, vector<int>(l + 1));
    }
    void addEdge(int u, int v){
        adj[u].pb(v);
        adj[v].pb(u);
    }
    void init(){
        dfs(1, -1); dfs1(1, -1);
    }
    void dfs(int u, int p){
        tin[u] = ++timer;
        up[u][0] = (p == -1 ? 1 : p);
        for(int i = 1; i <= l; i++){
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for(auto v : adj[u]){
            if(v != p){
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        }
        tout[u] = ++timer;
    } // O(nlogn)
    bool is_ancestor(int u, int v){
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    } // O(1)
    int lca(int u, int v){
        if(is_ancestor(u, v)) return u;
        if(is_ancestor(v, u)) return v;
        for(int i = l; i >= 0; i--){
            if(!is_ancestor(up[u][i], v)){
                u = up[u][i];
            }
        }
        return up[u][0];
    } // O(logn)
    int dist(int u, int v){
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    } // O(logn)
    int get_kth_ancestor(int u, int k){
        for(int i = l; i >= 0; i--){
            if(k & (1 << i)){
                u = up[u][i];
            }
        }
        return u;
    } // O(logn)
    void dfs1(int u, int p){
        subtree[u] = 1;
        for(auto v : adj[u]){
            if(v != p){
                dfs1(v, u);
                subtree[u] += subtree[v];
            }
        }
    } // O(n)
    bool is_leaf(int u){
        return u!=1 && SZ(adj[u]) == 1;
    } // O(1)
};

int best_path(int n, int k, int edges_[][2], int weights[]) {
    vector<tuple<int, int, ll>> edges;
    for(int i = 0; i < n-1; i++) edges_[i][0]++, edges_[i][1]++;
    Tree t(n + 2);
    for(int i = 0; i < n-1; i++) {
        edges.pb({edges_[i][0], edges_[i][1], 0LL});
        t.addEdge(edges_[i][0], edges_[i][1]);
    }
    t.init();
    for(int i = 0; i < n-1; i++) {
        get<2>(edges[i]) = weights[i];
    }
    vector<E> adj[n + 1]; for(int i = 0; i < SZ(edges); i++) {
        int u, v; ll w; tie(u, v, w) = edges[i];
        adj[u].pb({v, w}); adj[v].pb({u, w});
    }
    vector<ll> dist(n + 1, 0LL), dp(n + 1, 0LL);
    function<void(int, int)> init = [&](int u, int p) {
        for(auto [v, w] : adj[u]) if(v != p) {
            dp[v] = dp[u] + w; init(v, u);
        }
    }; init(1, 0);


    auto distance = [&](int u, int v) { return t.dist(u, v); };

    int ans = 1e9;
    map<ll, int> s[n + 1];
    
    auto MERGE = [&](int u, int v) {
        if(s[v].find(k + dp[u]) != s[v].end()) ans = min(ans, distance(u, s[v][k + dp[u]]));
        if(s[u].size() < s[v].size()) swap(s[u], s[v]);
        for(auto [d, l] : s[v]) {
            if(s[u].find(-d + 2*dp[u] + k) != s[u].end())
                ans = min(ans, distance(l, s[u][-d + 2*dp[u] + k]));
            if(!s[u].count(d)) s[u][d] = l;
            else s[u][d] = (t.depth[l] < t.depth[s[u][d]] ? l : s[u][d]);
        }
    };

    function<void(int, int)> dfs = [&](int u, int p) {
        for(auto [v, w] : adj[u]) if(v != p) {
            dfs(v, u); MERGE(u, v);
        }
        s[u][dp[u]] = u;
    };
    dfs(1, -1);
    return (ans == 1e9 ? -1 : ans);
}

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