Submission #1140501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140501		Sang	Race (IOI11_race)	C++20	0 / 100	2 ms	4936 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, ans = 1e9, sz[N], block[N], best[(int)(1e6) + 5], k;
vector<ii> G[N];

int get_subtree_size(int u, int par = 0){
    sz[u] = 1;
    for (ii &v :  G[u]){
        if (block[v.fi] || v.fi == par) continue;
        sz[u] += get_subtree_size(v.fi, u);
    }
    return sz[u];
}

int get_centroid(int u, int sub_sz, int par = 0){
    for (ii &v : G[u]){
        if (v.fi == par || block[v.fi]) continue;
        if (sz[v.fi] * 2 > sub_sz) return get_centroid(v.fi, sub_sz, u);
    }
    return u;
}

vector<ii> sub;
vi all;

void dfs(int u, int h, int dist, int par = 0){
    if (dist > k) return;
    sub.pb({dist, h});
    ans = min(ans, h + best[k - dist]);
    for (ii & v: G[u]){
        if (v.fi == par || block[v.fi]) continue;
        dfs(v.fi, h + 1, dist + v.se, u);
    }
}

void Centroid(int u){
    int centroid = get_centroid(u, get_subtree_size(u));
    block[centroid] = 1;
    best[0] = 0;
    for (ii & v: G[centroid]){
        if (block[v.fi]) continue;
        dfs(v.fi, 1, v.se, u);
        for (ii &x : sub){
            if (best[x.fi] == 1e9) all.pb(x.fi);
            best[x.fi] = min(best[x.fi], x.se);
        }
        sub.clear();
    }
    for (int &x : all) best[x] = 1e9;
    all.clear();
    for (ii &x : G[centroid]){
        if (block[x.fi]) continue;
        Centroid(x.fi);
    }

}

int best_path(int N, int K, int H[][2], int L[])
{
    FOR (i, 1, K) best[i] = 1e9;
    k = K;
    FOR (i, 0, N - 2){
        int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    Centroid(1);
    return (ans == 1e9 ? -1 : ans);
}

//int main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    cin >> n >> k;
//    FOR (i, 0, k) best[i] = 1e9;
//    FOR (i,1 , n - 1){
//        int u, v, w; cin >> u >> v >> w;
//        ++u; ++v;
//        G[u].pb({v, w});
//        G[v].pb({u, w});
//    }
//    Centroid(1);
//    cout << ans;
//
//}

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