제출 #1155999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155999		kitkat12	Race (IOI11_race)	C++20	100 / 100	466 ms	31672 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;
const int kmax = 1e6+3;
vector<pii> adj[nmax];
int ans=-1, K, sz[nmax], r[nmax], bes[kmax];

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 minimize(int &a, int b){
    if(a==-1 || a > b){
        a = b;
    }
}

void slv_cent(int u, int p, int sum, int cnt, bool sw){
    if(sum>K) return;
    if(sw){
        if(bes[K-sum]!=-1)
            minimize(ans,bes[K-sum]+cnt);
    }
    else{
        minimize(bes[sum], cnt);
    }

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

void del(int u, int p, int sum){
    if(sum>K)return;
    bes[sum]=-1;

    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;

    bes[0]=0;
    for(auto [v,len] : adj[u]){
        if(r[v]) continue;
        
        slv_cent(v,u,len,1,true);
        slv_cent(v,u,len,1,false);
    }

    //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);
    mem(bes,-1);
    solve(0);
    return ans;
}

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