Submission #1005366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005366		nikd	Race (IOI11_race)	C++17	0 / 100	0 ms	2396 KiB

race

// https://oj.uz/problem/view/IOI11_race
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> adj;
int n, k;
vector<bool> is_rem;
vector<int> sz;
vector<int> distL; //ll
vector<int> dist;
vector<int> k_dist;
vector<int> to_rem;
int sol;
int cont = 0;

void get_sz(int v, int e){
    sz[v]=1;
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        get_sz(u, v); sz[v] += sz[u];
    }
    return;
}

void get_dist(int v, int e){
    if(distL[v]<=k){
        k_dist[distL[v]] = min(k_dist[distL[v]], dist[v]);
    }
    to_rem[cont++]=v;
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        dist[u]=dist[v]+1;
        distL[u]=distL[v]+edge.second;
        get_dist(u, v);
    }
    return;
}


int find_centr(int v, int e, int siz){
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        if(sz[u] > siz/2) return find_centr(u, v, siz);
    }
    return v;
}

void decompose(int v, int siz){
    get_sz(v, v);
    int c = find_centr(v, v, siz);
    dist[c]=0; distL[c]=0;
    k_dist[0]=0;
    cont = 0;
    get_dist(c, c);
    for(int i = 0; i<siz; i++){
        if(distL[to_rem[i]]<=k){
            if(k_dist[k-distL[to_rem[i]]]!=INT_MAX){
                sol = min(sol, k_dist[k-distL[to_rem[i]]]+k_dist[distL[to_rem[i]]]);
            }
            k_dist[distL[to_rem[i]]]=INT_MAX;
        }
    }

    is_rem[c]=1;
    for(auto edge: adj[v]){
        int u = edge.first;
        if(is_rem[u]) continue;
        decompose(u, siz-1);
    }
}


int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    adj.resize(N);
    sz.resize(n);
    is_rem.resize(n, 0);
    distL.resize(n);
    dist.resize(n);
    k_dist.resize(k+1, INT_MAX);
    to_rem.resize(n);
    sol = INT_MAX;
    for(int i = 0; i<n-1; i++){
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    decompose(0, n);

    return (sol==INT_MAX ? -1 : sol);

}

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