Submission #1155407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155407		kitkat12	Race (IOI11_race)	C++20	0 / 100	4 ms	9024 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define li(i,a,b) for(int (i) = (a); (i)<(b); i++)
#define all(v) v.begin(), v.end()
#define mem(name, val) memset(name, val, sizeof(name))
#define endl '\n'

const int nmax = 2e5+3;
const int kmax = 1e6+3;
int n,k,ans, cnt[kmax], sz[nmax], r[nmax];
vector<pii> adj[nmax];

int dfs_sz(int v, int p = -1){
    sz[v]=1;
    for(auto [u,len] : adj[v]){
        if(u == p || r[u]) continue;
        sz[v] += dfs_sz(u,v);
    }
    return sz[v]; 
}

int get_center(int v, int ts, int p = -1){
    for(auto [u,len] : adj[v]){
        if(u == p || r[u]) continue; 
        if(sz[u] * 2 > ts) return get_center(u,ts,v);
    }
    return v;
}


void get_cnt(int sum, bool filling, int u, int p = -1, int depth = 1)
{
    if(sum > k) return;
    if(filling)
        cnt[sum] = min(cnt[sum],depth);
    else {
        if(cnt[k - sum] != -1){
            if(ans == -1) ans = depth+cnt[k-sum];
            else ans = min(ans, depth+cnt[k-sum]);
        }
    }
    for(auto [v, len]: adj[u]) {
        if(v == p || r[v]) continue;
        get_cnt(sum + len, filling, v, u, depth + 1);
    }
}


void del(int sum, int u, int p = -1)
{
    if(sum > k) return;
    cnt[sum] = -1;
    for(auto [v,len]: adj[u]) {
        if(v==p || r[v]) continue;
        del(sum + len, v, u);
    }
}

void build_decomp(int v = 0){
    int center = get_center(v, dfs_sz(v));
    r[center] = 1;
    cnt[0]=0;   

    for(auto [u,len] : adj[v]){
        if(r[u]) continue;
        get_cnt(len,false,v);
        get_cnt(len,true,v);
    }

    for(auto [u,len]: adj[v]){
        if(r[v])continue;
        del(len, u);
    }

    for(auto [u,len] : adj[v]){
        if(r[u]) continue;
        build_decomp(u);
    }
}



int best_path(int N, int K, int h[][2], int L[])
{
    n = N;
    k = K;
    for(int i = 0, u, v; i < n - 1; ++i) {
        u = h[i][0];
        v = h[i][1];
        adj[u].push_back(mp(v,L[i]));
        adj[v].push_back(mp(u,L[i]));
    }
    ans = -1;
    memset(cnt, -1, sizeof(cnt));
    build_decomp(0);
    return ans;
}

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