Submission #1005502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005502		nikd	Race (IOI11_race)	C++17	43 / 100	3035 ms	46408 KiB

race

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



vector<vector<pair<int, int>>> adj;
int n, k;
vector<bool> is_rem;
vector<int> sz;
vector<ll> distL; //ll
vector<int> dist;
unordered_map<int, int> buf_k_dist;
unordered_map<int, int> k_dist;
int sol;



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){
        if(buf_k_dist.count(distL[v])==0) buf_k_dist[distL[v]] = dist[v];
        else if(buf_k_dist[distL[v]] > dist[v]) buf_k_dist[distL[v]] = dist[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;
    for(auto edge: adj[c]){
        int u = edge.first;
        if(is_rem[u]) continue;
        dist[u]=1;
        distL[u] = edge.second;
        get_dist(u, c);
        for(auto [key, val] : buf_k_dist){
            if(k_dist.count(k-key)!=0){
                sol = min(sol, val+ k_dist[k-key]);
            }
        }
        for(auto [key, val] : buf_k_dist){
            if(k_dist.count(key)!=0){
                k_dist[key] = min(k_dist[key], val);
            }
            else k_dist[key] = val;
        }
        buf_k_dist.clear();
    }

    
    k_dist.clear();

    get_sz(c, c);


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


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);

    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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57