Submission #33990

#	Time	Username	Problem	Language	Result	Execution time	Memory
33990		TAMREF	경주 (Race) (IOI11_race)	C++11	0 / 100	108 ms	13236 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]);
        depv.insert(dep[now]);
        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]);
    dep[cen] = 0;
    memset(chk,inf,sizeof(chk));
    for(pil &p : G[cen]){
        if(del[p.va]) continue;
        dep[p.va] = 1;
        par[p.va] = cen;
        fill(nowchk,nowchk+mk,inf);
        depv.clear();
        dfs(p.va,p.vb);
        for(int u : depv) chk[u] = min(chk[u],nowchk[u]);
    }
    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]);
    }
    dnc(0);
    return ans;
}

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