Submission #904921

#	Time	Username	Problem	Language	Result	Execution time	Memory
904921		a_l_i_r_e_z_a	Race (IOI11_race)	C++17	0 / 100	3 ms	12636 KiB

race

// In the name of God

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 2e5 + 5, maxk = 1e6  + 5;
const int inf = 1e9 + 7;
ll n, k, ans = inf, sz[maxn], h[maxn], mn[maxk];
vector<pii> adj[maxn];
vector<int> vec;
bool mark[maxn];

void get_sz(int v, int p = -1){
    sz[v] = 1;
    for(auto [u, w]: adj[v]){
        if(u != p && !mark[u]){
            get_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

int find(int v, int s, int p = -1){
    for(auto [u, w]: adj[v]) if(u != p && !mark[u] && sz[u] * 2 > s) return find(u, s, v);
    return v;
}

void dfs(int v, int h1, int h2, int p, bool keep){
    if(h2 > k) return;
    if(keep){
        smin(mn[h2], 1ll * h1);
        vec.pb(h2);
    }
    else smin(ans, h1 + mn[k - h2]);
    for(auto [u, w]: adj[v]) if(u != p && !mark[u]) dfs(u, h1 + 1, h2 + w, v, keep);
}

void centroid_decomp(int v = 0){
    get_sz(v);
    v = find(v, sz[v]);
    mn[0] = 0;
    for(auto [u, w]: adj[v]){
        if(!mark[u]){
            dfs(u, 1, w, v, 0);
            dfs(u, 1, w, v, 1);
        }
    }
    mn[0] = inf;
    for(auto u: vec) mn[u] = inf;
    vec.clear();
    mark[v] = 1;
    for(auto [u, w]: adj[v]) if(!mark[u]) centroid_decomp(u);
} 

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0; i < n - 1; i++){
        int u = H[i][0], v = H[i][1], w = L[i];
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    centroid_decomp();
    return (ans >= inf ? -1 : ans);
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     fill(mn, mn + maxk, inf);
//     cin >> n >> k;
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         adj[u].pb(mp(v, w));
//         adj[v].pb(mp(u, w));
//     }
//     centroid_decomp();
//     cout << (ans >= inf ? -1 : ans) << '\n';

//     return 0;
// }

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