Submission #1218806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218806		kiteyu	Race (IOI11_race)	C++20	100 / 100	1004 ms	49012 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
int n, l, r;
ll k;
vector<pair<int,int>> adj[N];
int sub_sz[N];
bool deleted[N];

int get_sz(int x,int p = 0){
    sub_sz[x] = 1;
    for(pair<int,int> i : adj[x]){
        if(i.first == p || deleted[i.first]) continue;
        sub_sz[x] += get_sz(i.first,x);
    }
    return sub_sz[x];
}

int find_cen(int x, int sz, int p = 0){
    for(pair<int,int> i : adj[x]){
        if(i.first == p || deleted[i.first]) continue;
        if(sub_sz[i.first] * 2 > sz) return find_cen(i.first,sz,x);
    }
    return x;
}
ll sum[N];
int ans = inf;
int mx = 0, H[N];
vector<pair<int,int>> v;
int Sz;
map<ll,int> mp;

//void upd(int idx, int val){
//    for(;idx <= Sz  ; idx += (idx & (-idx)))
//        bit[idx] += val;
//}
//
//ll get(int idx){
//    ll s = 0;
//    for(;0 < idx ; idx -= (idx & (-idx)))
//        s += bit[idx];
//    return s;
//}

void get_dist(int x, int p, ll h, int cur){
   // cout << x << '.' << h << '.' << mp[k - h] << '\n';
    if(h > k) return;
    if(h == k) {ans = min(ans,cur); return;}
    else if(mp[k - h]) {
        //cout << x << '.' << cur << '.' << mp[k - h] << '\n';
        ans = min(ans,cur + mp[k - h]);
    }
    v.push_back({h,cur});


    for(pair<int,int> i : adj[x]){
        if(i.first == p || deleted[i.first]) continue;
        get_dist(i.first,x,h + i.second,cur + 1);
    }
    return;
}

void build_centroid(int x){
    Sz = get_sz(x);
    x = find_cen(x,Sz);
    mx = 0;
    deleted[x] = 1;
    mp.clear();

    for(pair<int,int> i : adj[x]) {
        if(deleted[i.first]) continue;
        v.clear();
        get_dist(i.first,x,i.second,1);

        for(pair<int,int> j : v)
        {
            if(!mp[j.first]) mp[j.first] = j.second;
            else mp[j.first] = min(mp[j.first],j.second);
        }
    }

    for(pair<int,int> i : adj[x]){
        if(deleted[i.first]) continue;
        build_centroid(i.first);
    }
}

int best_path(int N, int K, int H[][2],int L[]){
   // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    n = N;
    k = K;
    for(int i = 0,x,y,z; i < n - 1; ++i){
        x = H[i][0];
        y = H[i][1];
        z = L[i];
        x++;y++;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    build_centroid(1);
    return (ans == inf ? -1 : ans);
}

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