Submission #1144420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144420		gazizmadi11	Race (IOI11_race)	C++20	100 / 100	1246 ms	48292 KiB

race

//gm  --- akezhon
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define tm (tl+tr)/2
#define TL v+v, tl, tm
#define TR v+v+1, tm+1, tr
#define DA l <= tl && tr <= r
#define NE r < tl || tr < l
#define double long double
//#define int long long 
using namespace std;

const int nN=3e5+7;
const int mod=998244353;
const int inf=2e9;

vector <pii> g[nN];
int sz[nN];
bool del[nN];
int n, k;
map<int,int>mp;
int ans;

int cent(int v, int par, int s){
    for(auto [u, col] : g[v]){
        if(u != par && del[u] == 0 && sz[u]*2 > s)return cent(u, v, s);
    }
    return v;
}
void get_sz(int v, int par){
    sz[v] = 1;
    for(auto [u, col] : g[v]){
        if(u != par && del[u] == 0){
            get_sz(u, v);
            sz[v] += sz[u];
        }
    }
}
void get(int v, int p, int a, int b){
    if(a > k)return;
    if(a==k)ans = min(ans, b);
    else if(mp[k-a])ans = min(ans, b+mp[k-a]);
    for(auto [u, col] : g[v]){
        if(del[u] == 1 || u == p)continue;
        get(u, v, a+col, b+1);
    }
}
void add(int v, int p, int a, int b){
    if(a > k)return;
    if(mp[a] == 0){
        if(a)mp[a] = b;
    }
    else mp[a] = min(mp[a], b);
    for(auto [u, col] : g[v]){
        if(del[u] == 1 || u == p)continue;
        add(u, v, a+col, b+1);
    }
}
void build(int v){
    get_sz(v, v);
    v = cent(v, v, sz[v]);
    del[v] = 1;

    mp.clear();
    mp[0] = 0;
    for(auto [u, col] : g[v]){
        if(del[u] == 1)continue;
        get(u, v, col, 1);
        add(u, v, col, 1);
    }
    for(auto [u, col] : g[v]){
        if(del[u] == 0)build(u);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0; i < N-1; i++){
        int a = H[i][0], b = H[i][1], col = L[i];
        g[a].pb({b, col});
        g[b].pb({a, col});
    }
    ans = 1e9;
    build(0);
    if (ans == 1e9)ans = -1;    
    return ans;
}

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