Submission #525514

#	Time	Username	Problem	Language	Result	Execution time	Memory
525514		NekoRolly	Race (IOI11_race)	C++17	100 / 100	511 ms	31592 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+4;
const int inf = 1e9;

struct Cd{
    vector<pair<int,int>> adj[N];
    int vis[N],sz[N],up[N],mn[5*N];
    int ans,k;

    void init(int _k){
        for (int i=0; i<5*N; i++) mn[i] = inf;
        ans = inf; k = _k;
    }

    int find(int u,int p,int Sz){
        sz[u] = 1;
        int val = 0, x = 0;
        for (auto [v, w] : adj[u]) if (v != p && !vis[v]){
            x ^= find(v, u, Sz); sz[u] += sz[v];
            val = max(val, sz[v]);
        }
        if (max(val, Sz-sz[u]) <= Sz/2) up[x = u] = p;
        return x;
    }

    void dfs(int u,int p,int dis,int h,int f){
        if (dis > k) return; 
        if (f == 0) ans = min(ans, mn[k-dis]+h);
        if (f == 1) mn[dis] = min(mn[dis], h);
        if (f == 2) mn[dis] = inf; 
        for (auto [v, w] : adj[u]) if (v != p && !vis[v])
            dfs(v, u, dis+w, h+1, f);
    }

    void calc(int u){
        mn[0] = 0;
        for (auto [v, w] : adj[u]) if (!vis[v]){
            dfs(v, u, w, 1, 0);
            dfs(v, u, w, 1, 1);
        }
        dfs(u, -1, 0, 0, 2);
    }

    void build(int u,int Sz){
        u = find(u, -1, Sz);
        if (up[u] != -1) sz[up[u]] = Sz-sz[u];
        vis[u] = 1; calc(u);
        for (auto [v, w] : adj[u]) if (!vis[v])
            build(v, sz[v]);
    }
} d;

int best_path(int n, int k, int H[][2], int L[]){
    for (int i=0; i<n-1; i++){
        d.adj[H[i][0]+1].push_back({H[i][1]+1, L[i]});
        d.adj[H[i][1]+1].push_back({H[i][0]+1, L[i]});
    }

    d.init(k);
    d.build(1, n);

    return (d.ans == inf ? -1 : d.ans);
}
/*
int main(){
    int n,k,H[N][2],L[N]; cin >> n >> k;

    for (int i=0; i<n-1; i++) cin >> H[i][0] >> H[i][1] >> L[i];

    cout << best_path(n, k, H, L) << "\n";
    return 0;
}
*/

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