Submission #527735

#	Time	Username	Problem	Language	Result	Execution time	Memory
527735		KindaNameless	Race (IOI11_race)	C++14	100 / 100	959 ms	39176 KiB

race

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long

struct centroid_tree{
    vector<vector<pair<int, int>>> adj;
    vector<bool> vis;
    vector<int> par, sz;
    vector<ll> cnt;
    map<int, int> paths;
    int N, K, answer;

    void init(int _N, int len){
        int N = _N; K = len;
        adj = vector<vector<pair<int, int>>>(N+2, vector<pair<int, int>>());
        vis = vector<bool>(N+2);
        par = vector<int>(N+2);
        sz  = vector<int>(N+2);
        answer = 1e9;
    }

    void edge(int u, int v, int w){
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    int get_size(int cur, int p = -1){
        sz[cur] = 1;
        for(pair<int, int> ch : adj[cur]){
            if(ch.first != p && !vis[ch.first]){
                sz[cur] += get_size(ch.first, cur);
            }
        }
        return sz[cur];
    }

    int find_centroid(int cur, int p, int total){
        for(pair<int, int> ch : adj[cur]){
            if(sz[ch.first] > total/2 && ch.first != p && !vis[ch.first]){
                return find_centroid(ch.first, cur, total);
            }
        }
        return cur;
    }

    void calc(int cur, int p, int depth, int step, int flag){
        if(depth > K)return;
        if(flag){
            if(!paths.count(depth)){
                paths[depth] = step;
            }
            else{
                paths[depth] = min(paths[depth], step);
            }
        }
        else{
            if(paths.count(K - depth)){
                answer = min(answer, step + paths[K - depth]);
            }
        }
        for(pair<int, int> ch : adj[cur]){
            if(ch.first != p && !vis[ch.first]){
                calc(ch.first, cur, depth + ch.second, step + 1, flag);
            }
        }
    }

    void build(int cur = 1, int p = -1){
        get_size(cur);
        int cen = find_centroid(cur, p, sz[cur]);
        vis[cen] = 1;
        par[cen] = p;

        paths[0] = 0;
        for(pair<int, int> ch : adj[cen]){
            if(!vis[ch.first]){
                calc(ch.first, cen, ch.second, 1, 0);
                calc(ch.first, cen, ch.second, 1, 1);
            }
        }
        paths.clear();

        for(pair<int, int> ch : adj[cen]){
            if(!vis[ch.first]){
                build(ch.first, cen);
            }
        }
    }
};

centroid_tree CT;

int best_path(int N, int K, int H[][2], int L[]){
    CT.init(N, K);
    for(int i = 0; i < N-1; ++i){
        int u = H[i][0] + 1, v = H[i][1] + 1;
        CT.edge(u, v, L[i]);
    }

    CT.build();

    int answer = CT.answer;

    return (answer == 1e9 ? -1 : answer);
}

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