Submission #1005390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005390		nikd	Race (IOI11_race)	C++17	0 / 100	1 ms	2396 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;
vector<array<int, 4>> 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, int sb){
    if(distL[v]<=k){
        if(dist[v]<k_dist[distL[v]][0]){
            if(k_dist[distL[v]][1]!=sb){
                k_dist[distL[v]][3] = k_dist[distL[v]][1];
                k_dist[distL[v]][2] = k_dist[distL[v]][0];
            }
            k_dist[distL[v]][0] = dist[v];
            k_dist[distL[v]][1] = sb;
            
        }
        else if(k_dist[distL[v]][1]!=sb && dist[v]<k_dist[distL[v]][2]){
            k_dist[distL[v]][2] = dist[v];
            k_dist[distL[v]][3] = sb;

        }

        if(k_dist[k-distL[v]][1]!=sb && k_dist[k-distL[v]][0] != INT_MAX){
            sol = min(sol, k_dist[k-distL[v]][0] + dist[v]);
        }
        else if(k_dist[k-distL[v]][2] != INT_MAX ){
            sol = min(sol, k_dist[k-distL[v]][3] + 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;
        if(v==e) sb = u;
        get_dist(u, v, sb);
    }
    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;
    cont = 0;
    get_dist(c, c, -1);
    for(int i = 0; i<siz; i++){
        if(distL[to_rem[i]]<=k){
            k_dist[distL[to_rem[i]]]={INT_MAX, INT_MAX, INT_MAX, INT_MAX};
        }
    }
    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);
    
    k_dist.resize(k+1, {INT_MAX, INT_MAX, INT_MAX, 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