Submission #1000205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000205		Icelast	Race (IOI11_race)	C++17	100 / 100	398 ms	107092 KiB

race

#include "race.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Tree{
    int n, root;
    vector<int> depth, head, sz, pa;
    vector<int> f;
    Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
        depth.resize(n+1, -1);
        head.resize(n+1);
        sz.resize(n+1, 0);
        pa.resize(n+1, -1);
        auto rootTree = [&](auto rootTree, int u, int p) -> void{
            depth[u] = depth[p]+1;
            pa[u] = p;
            sz[u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                rootTree(rootTree, v, u);
                sz[u] += sz[v];
            }
        };
        rootTree(rootTree, root, 0);
        auto decompose = [&](auto decompose, int u, int h) -> void{
            head[u] = h;
            int heavy = -1;
            for(int v : adj[u]){
                if(v == pa[u]) continue;
                if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
            }
            if(heavy != -1) decompose(decompose, heavy, h);
            for(int v : adj[u]){
                if(v == pa[u] || v == heavy) continue;
                decompose(decompose, v, v);
            }
        };
        decompose(decompose, root, root);
        f = [&]{
            vector<array<int, 2>> first(n+1);
            vector<array<int, 2>> second(n+1);
            function<void(int, int)> dfs0 = [&](int u, int p) {
                first[u] = second[u] = {0, -1};
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    dfs0(v, u);
                    auto fetch = first[v];
                    fetch[0] += 1;
                    fetch[1] = v;
                    if (fetch > first[u]) {
                        swap(fetch, first[u]);
                    }
                    if (fetch > second[u]) {
                        swap(fetch, second[u]);
                    }
                }
            };
            dfs0(1, 0);

            function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    auto fetch = first[u][1] == v ? second[u] : first[u];
                    fetch[0] += 1;
                    fetch[1] = u;
                    if (fetch > first[v]) {
                        swap(fetch, first[v]);
                    }
                    if (fetch > second[v]) {
                        swap(fetch, second[v]);
                    }
                    dfs(v, u);
                }
            };
            dfs(1, 0);
            vector<int> f(n+1);
            for (int u = 1; u <= n; u++) {
                f[u] = first[u][0];
            }
            return f;
        }();
    };
    int lca(int u, int v){
        for(; head[u] != head[v]; v = pa[head[v]]){
            if(depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if(depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u, v)];
    }
};
int best_path(int N, int K, int H[][2], int L[])
{
    int n = N;
    vector<vector<pair<ll, ll>>> adj(n+1);
    for(int i = 0; i < n-1; i++){
        int u = H[i][0], v = H[i][1];
        u++; v++;
        adj[u].push_back({v, L[i]});
        adj[v].push_back({u, L[i]});
    }
    vector<int> pa(n+1), depth(n+1, 0);
    depth[0] = -1;
    vector<ll> path(n+1);
    auto rtree = [&](auto rtree, int u, int p, ll len) -> void{
        path[u] = len;
        depth[u] = depth[p]+1;
        pa[u] = p;
        for(auto it : adj[u]){
            int v = it.first, w = it.second;
            if(v == p) continue;
            rtree(rtree, v, u, len+w);
        }
    };
    rtree(rtree, 1, 0, 0);
    vector<map<ll, ll>> mp(n+1);
    ll ans = INF;
    auto dfs = [&](auto dfs, int u, int p) -> void{
        mp[u][path[u]] = depth[u];
        for(auto it : adj[u]){
            int v = it.first;
            if(v == p) continue;
            dfs(dfs, v, u);
            if(mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
            for(auto it : mp[v]){
                if(mp[u].count(K+2*path[u]-it.first)){
                    ans = min(ans, mp[u][K+2*path[u]-it.first]+it.second-2*depth[u]);
                }
            }
            for(auto it : mp[v]){
                if(mp[u].count(it.first)){
                    mp[u][it.first] = min(mp[u][it.first], it.second);
                }else{
                    mp[u][it.first] = it.second;
                }
            }
        }
        if(mp[u].count(K+path[u])){
            ans = min(ans, mp[u][K+path[u]]-depth[u]);
        }
    };
    dfs(dfs, 1, 0);
    if(ans == INF) ans = -1;
    return ans;
}

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