Submission #1155988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155988		kitkat12	경주 (Race) (IOI11_race)	C++20	0 / 100	3 ms	7488 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 sz[nmax], r[nmax];
int K; 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;
}

void gather(int u, int p, int sum, int cnt, vector<pii> &vec){
    vec.pb({sum,cnt});
    for(auto [v,len]: adj[u]){
        if(p==v || r[v]) continue;
        gather(v,u,sum+len,cnt+1,vec);
    }
}

vector<ll> bes(nmax,INT_MAX);

void del(int u, int p, int sum){
    bes[sum]=INT_MAX;

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

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

    for(auto [v,len] : adj[u]){
        if(r[v]) continue;
        
        vector<pii> vec;
        gather(v,u,len,1,vec);

        for(auto &p : vec){
            bes[K] = min(bes[K], bes[K-p.F]+p.S);
            ans=min(ans,bes[K]);
            bes[p.F] = min(bes[p.F], p.S);
        }
    }

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

    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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57