Submission #556204

#	Time	Username	Problem	Language	Result	Execution time	Memory
556204		Dan4Life	Race (IOI11_race)	C++17	43 / 100	3088 ms	47112 KiB

race

#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;

int answ, KK, cnt[1000010], subtree[maxn];
set<pair<int,int>> adj[maxn];

void dfs(int s, int p){
    subtree[s]=1;
    for(auto x : adj[s]){
        int u = x.first;
        if(u==p) continue;
        dfs(u,s), subtree[s]+=subtree[u];
    }
}

void dfs2(int s, int p, int dep, int weight, bool ok){
    if(weight>KK) return;
    for(auto u : adj[s])
        if(u.first!=p)
            dfs2(u.first,s,dep+1,weight+u.second, ok);
    int D = KK-weight;
    if(!ok) answ = min(answ, dep+cnt[D]);
    else cnt[weight] = min(cnt[weight], dep);
}

int find_centroid(int s, int p, int sz){
    for(auto u : adj[s])
        if(u.first!=p and subtree[u.first]>sz/2)
            return find_centroid(u.first, s, sz);
    return s;
}


void centroid_decomp(int s, int p){
    dfs(s,-1); int sz = subtree[s];
    int centroid = find_centroid(s,-1,sz);

    for(int i = 1; i <= KK; i++) cnt[i]=cnt[KK+1];
    for(auto w : adj[centroid]){
        int u = w.first; if(u==p) continue;
        dfs2(u,centroid,1,w.second,0), dfs2(u,centroid,1,w.second,1);
    }
    while(!adj[centroid].empty()){
        int x = adj[centroid].begin()->first;
        adj[x].erase(adj[x].lower_bound({centroid,-1}));
        adj[centroid].erase(adj[centroid].begin());
        centroid_decomp(x,centroid);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    answ = N+1; KK = K; cnt[0]=0;
    for(int i = 1; i <= K+1; i++) cnt[i]=N+1;
    for(int i = 0; i < N-1; i++)
        adj[++H[i][0]].insert({++H[i][1],L[i]}),
        adj[H[i][1]].insert({H[i][0],L[i]});
    centroid_decomp(1,-1);
    return (answ==N+1?-1:answ);
}

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