Submission #736532

#	Time	Username	Problem	Language	Result	Execution time	Memory
736532		Skywk	Race (IOI11_race)	C++17	100 / 100	573 ms	54940 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAX = 1e6;
vector<pair<int, int>> graph[MAXN+1];
int sz[MAXN+1];
bitset<MAXN+1> usd;
int find_centroid(int root){
    function<void(int, int)> get_sz = [&](int v, int p){
        sz[v] = 1;
        for(auto [u, d] : graph[v]){
            if(usd[u] || u == p) continue;
            get_sz(u, v);
            sz[v] += sz[u];
        }
    };
    get_sz(root, -1);
    function<int(int, int)> dfs = [&](int v, int p){
        for(auto [u, d] : graph[v]){
            if(usd[u] || u == p) continue;
            if(sz[u] > sz[root]/2) return dfs(u, v);
        }
        return v;
    };
    return dfs(root, -1);
}
tuple<int, int, int, int> best[MAX+1];//best and second best edges to reach dist
int TRACK;// K
int ANS; // answer
void update(const int &root, int v, int p, int dist, int lvl){
    if(dist > TRACK) return;
    //update best values
    auto [l1, u1, l2, u2] = best[dist];
    if(l1 != -1 && l2 != -1){
        if(lvl < l1){
            if(root == u1){
                l1 = lvl, u1 = root;
            }
            else{
                l2 = l1, u2 = l2;
                l1 = lvl, u1 = root;
            }
        }
        else if(lvl < l2){
            if(root == u1){

            }
            else{
                l2 = lvl, u2 = root;
            }
        }
    }
    else if(l1 == -1){
        l1 = lvl, u1 = root;
    }
    else if(l2 == -1){
        if(lvl < l1){
            if(root == u1){
                l1 = lvl, u1 = root;
            }
            else{
                l2 = l1, u2 = u1;
                l1 = lvl, u1 = root;
            }
        }
    }
    best[dist] = {l1, u1, l2, u2};
    for(auto [u, d] : graph[v]){
        if(usd[u] || u == p) continue;
        update(root, u, v, dist + d, lvl+1);
    }
}
void calc(const int &root, int v, int p, int dist, int lvl){
    if(dist > TRACK) return;
    auto [l1, u1, l2, u2] = best[TRACK - dist];
    if(l1 != -1 && root != u1){
        ANS = min(ANS, l1 + lvl);
    }
    else if(l2 != -1){
        ANS = min(ANS, l2 + lvl);
    }
    for(auto [u, d] : graph[v]){
        if(usd[u] || u == p) continue;
        calc(root, u, v, dist + d, lvl + 1);
    }
}
void clear(int v, int p, int dist){
    if(dist > TRACK) return;
    best[dist] = {-1, -1, -1, -1};
    for(auto [u, d] : graph[v]){
        if(usd[u] || u == p) continue;
        clear(u, v, dist + d);
    }
}
void centroid_decomposition(int root){
    function<void(int)> dfs = [&](int v){
        int c = find_centroid(v);
        usd[c] = 1;
        for(auto [u, d] : graph[c]){
            if(usd[u]) continue;
            dfs(u);
        }
        for(auto [u, d] : graph[c]){
            if(usd[u]) continue;
            update(u, u, c, d, 1);
        }
        if(get<0>(best[TRACK]) != -1){
            ANS = min(ANS, get<0>(best[TRACK]));
        }
        for(auto [u, d] : graph[c]){
            if(usd[u]) continue;
            calc(u, u, c, d, 1);
        }
        clear(c, -1, 0);

        usd[c] = 0;
    };
    dfs(root);
}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0; i<N-1; i++){
        graph[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        graph[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
    }
    TRACK = K;
    for(int i=0; i<=MAX; i++){
        best[i] = {-1, -1, -1, -1};
    }
    ANS = N;
    centroid_decomposition(1);
    return (ANS == N ? -1 : ANS);
}

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