Submission #33991

#	Time	Username	Problem	Language	Result	Execution time	Memory
33991		TAMREF	경주 (Race) (IOI11_race)	C++11	0 / 100	7 ms	5452 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;

typedef long long ll;
typedef pair<int,ll> pil;
const int mx = 2e5+5;
const int mk = 1e6+1;
const int inf = 5e5;

vector<pil> G[mx];
unordered_set<int> depv;

int cnt[mx], par[mx], dep[mx];
int chk[mk], nowchk[mk];
int K_g, N_g, ans=5e5;
bool del[mx];

void setcnt(int r){
    cnt[r] = 1;
    for(pil &p : G[r]){
        if(del[p.va] || p.va == par[r]) continue;
        par[p.va] = r;
        setcnt(p.va);
        cnt[r] += cnt[p.va];
    }
}

int centroid(int now, int num){
    for(pil &p : G[now]){
        if(del[p.va] || p.va == par[now]) continue;
        if(cnt[p.va]>num/2) return centroid(p.va,num);
    }
    return now;
}

void dfs(int now, ll sum){
    if(sum <= K_g){
        nowchk[sum] = min(nowchk[sum], dep[now]);
        //printf("now = %d, sum = %lld, chk[%lld]=%d, nowchk[%lld]=%d\n",now,sum,K_g-sum,chk[K_g-sum],sum,nowchk[sum]);
        depv.insert(sum);
        ans = min(ans, dep[now] + chk[K_g-sum]);
    }
    for(pil &p : G[now]){
        if(del[p.va] || p.va == par[now]) continue;
        par[p.va] = now;
        dep[p.va] = dep[now] + 1;
        dfs(p.va, sum + p.vb);
    }
}

void dnc(int r){
    setcnt(r);
    int cen = centroid(r,cnt[r]);
    //printf("----------centroid is %d----------\n",cen);
    dep[cen] = 0;
    fill(chk,chk+K_g+1,inf);
    for(pil &p : G[cen]){
        if(del[p.va]) continue;
        dep[p.va] = 1;
        par[p.va] = cen;
        for(int u : depv) nowchk[u] = inf;
        depv.clear();
        dfs(p.va,p.vb);
        for(int u : depv){
            //printf("%d in check\n",u);
            chk[u] = min(chk[u],nowchk[u]);
        }
    }
    //puts("----------------------------");
    del[cen] = true;
    for(pil &p : G[cen]){
        if(del[p.va]) continue;
        dnc(p.va);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    N_g = N, K_g = K;
    for(int i=0;i<N-1;i++){
        G[H[i][0]].emplace_back(H[i][1],L[i]);
        G[H[i][1]].emplace_back(H[i][0],L[i]);
    }
    fill(nowchk,nowchk+K+1,inf);
    dnc(0);
    return ans==inf?-1:ans;
}

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