Submission #1197791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197791		RaduM	경주 (Race) (IOI11_race)	C++20	0 / 100	6 ms	14092 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

vector < set < pair <int, int> > > G(200005);

int dp[200005];

int h[200005];
int h2[200005];

int best[1000005];

int n, k, rez;

void dfs(int nod, int t){
    dp[nod] = 1;
    for(auto x : G[nod]){
        if(x.first == t) continue;
        dfs(x.first, nod);
        dp[nod] += dp[x.first];
    }
}

int centroid(int nod, int t, int sz){
    for(auto x : G[nod]){
        if(x.first == t) continue;
        if(dp[x.first] > (sz >> 1)) return centroid(x.first, nod, sz);
    }
    return nod;
}

void dfs2(int nod, int t, int flag){
    if(!flag) rez = min(rez, h[nod] + best[k - h2[nod]]);
    else if(flag == 1) best[h2[nod]] = min(best[h2[nod]], h[nod]);
    else best[h2[nod]] = inf;
    for(auto x : G[nod]){
        if(x.first == t) continue;
        h2[x.first] = h2[nod] + x.second;
        h[x.first] = h[nod] + 1;
        if(h2[x.first] > k) continue;
        dfs2(x.first, nod, flag);
    }
}

void build_centroid_tree(int nod){
    dfs(nod, 0);
    int c = centroid(nod, 0, dp[nod]);

    h[c] = h2[c] = 0;
    for(auto x : G[c]){
        h2[x.first] = h2[c] + x.second;
        h[x.first] = h[c] + 1;
        if(h2[x.first] > k) continue;
        dfs2(x.first, c, 0);
        dfs2(x.first, c, 1);
    }
    rez = min(rez, best[k]);
    dfs2(c, 0, 2);

    vector <int> v;
    for(auto x : G[c]) v.push_back(x.first);
    G[c].clear();
    for(auto x : v){
        G[x].erase(G[x].lower_bound({c, 0}));
        build_centroid_tree(x);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    int i;
    rez = inf;
    n = N;
    k = K;
    for(i = 0; i < n - 1; i++){
        H[i][0]++;
        H[i][1]++;
        G[H[i][0]].insert({H[i][1], L[i]});
        G[H[i][1]].insert({H[i][0], L[i]});
    }
    memset(best, 0x3f, sizeof best);
    build_centroid_tree(1);
    return rez;
}

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