Submission #1156010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156010		kitkat12	Race (IOI11_race)	C++20	100 / 100	970 ms	45008 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 F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 2e5+3;
vector<pii> adj[nmax];
int K, sz[nmax], r[nmax];
ll ans = INT_MAX;

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

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

vector<pii> vec;

void slv_cent(int u, int p, int sum, int cnt){
    if(sum>K || cnt > ans) return;

    vec.pb({sum,cnt});

    for(auto [v,len]: adj[u]){
        if(p==v || r[v]) continue;
        slv_cent(v,u,sum+len,cnt+1);
    }
}

void solve(int u){
    u = get_cent(u,dfs_sz(u));
    r[u]=1;

    map<int, int> bes;
    for(auto [v,len] : adj[u]){
        if(r[v]) continue;

        slv_cent(v,u,len,1);
        
        for(auto &p : vec){
            if(bes.find(K-p.F) != bes.end()){
                ans = min(ans, bes[K-p.F]+p.S);
            }
            else if(p.F == K){
                ans = min(ans, p.S);
            }
        }

        for(auto &p : vec){
            if(bes.find(p.F) == bes.end()){
                bes[p.F]=p.S;
            }
            else{
                bes[p.F] = min(p.S,bes[p.F]);
            }
        }
        vec.clear();
    }    

    for(auto [v,_] : adj[u]){
        if(!r[v]) solve(v);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    K=k;
    li(i,0,n-1){
        adj[h[i][0]].pb({h[i][1],l[i]});
        adj[h[i][1]].pb({h[i][0],l[i]});
    }
    mem(r,0);
    solve(0);
    return ans==INT_MAX?-1:ans;
}

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