Submission #1103033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103033		InvMOD	Race (IOI11_race)	C++14	100 / 100	226 ms	38388 KiB

race

#include<bits/stdc++.h>

#define fi first
#define se second

using namespace std;

template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int _N = 2e5+5, _K = 1e6+5, inf = 1e9;

int n, k, sz[_N];
int MinDist[_K], miniDist;
bool del[_N];
vector<pair<int,int>> adj[_N];

int get_Size(int x, int p){
    sz[x] = 1;
    for(pair<int,int> e : adj[x]){
        int v = e.fi;
        if(v != p && !del[v]){
            sz[x] += get_Size(v, x);
        }
    }
    return sz[x];
}

int Centroid(int x, int p, int trsz){
    for(pair<int,int> e : adj[x]){
        int v = e.fi;
        if(v != p && !del[v]){
            if((sz[v]<<1) > trsz){
                return Centroid(v, x, trsz);
            }
        }
    }
    return x;
}

queue<int> save;
stack<pair<int,int>> subtr;

void dfs(int x, int p, int cur_dist, int cur_height){
    if(MinDist[k - cur_dist] != inf){
        ckmn(miniDist, MinDist[k - cur_dist] + cur_height);
    }
    for(pair<int,int> e : adj[x]){
        int v = e.fi, w = e.se;
        if(del[v] || v == p) continue;

        if(cur_dist <= k - w && cur_height+1 <= miniDist) dfs(v, x, cur_dist+w, cur_height+1);
        if(p == -1){
            while(!subtr.empty()){
                pair<int,int> info = subtr.top(); subtr.pop();

                int dist = info.fi, mnH = info.se;
                ckmn(MinDist[dist], mnH);
            }
        }
    }
    if(p != -1){
        save.push(cur_dist);
        subtr.push(make_pair(cur_dist, cur_height));
    }
    else{
        while(!save.empty()){
            int dist = save.front(); save.pop();
            MinDist[dist] = inf;
        }
    }
    return;
}

void decompose(int x){
    x = Centroid(x, -1, get_Size(x, -1));
    del[x] = true;

    dfs(x, -1, 0, 0);

    for(pair<int,int> e : adj[x]){
        int v = e.fi;
        if(!del[v]) decompose(v);
    }
    return;
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for(int i = 0; i < n-1; i++){
        int u = H[i][0]+1, v = H[i][1]+1, w = L[i];
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    miniDist = inf;
    for(int i = 1; i <= k; i++){
        MinDist[i] = inf;
    }
    decompose(1);
    return (miniDist == inf ? -1 : miniDist);
}

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