Submission #160645

#	Time	Username	Problem	Language	Result	Execution time	Memory
160645		jhnah917	Race (IOI11_race)	C++14	0 / 100	21 ms	18168 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;

typedef pair<int, int> p;

int n, k;
vector<p> g[202020];
vector<int> init;

int sz[202020], use[202020], chk[1010101];

int getSize(int v, int par){
    sz[v] = 1;
    for(auto i : g[v]){
        if(i.x == par || use[i.x]) continue;
        sz[i.x] += getSize(i.x, v);
    }
    return sz[v];
}

int getCent(int v, int par, int cnt){
    for(auto i : g[v]){
        if(i.x == par || use[i.x]) continue;
        if(sz[i.x] > cnt/2) return getCent(i.x, v, cnt);
    }
    return v;
}

void update(int now, int prv, int dst, int dep){
    if(dep > k) return;
    chk[dst] = min(chk[dst], dep);
    init.push_back(dst);
    for(auto i : g[now]){
        if(i.x == prv || use[i.x]) continue;
        update(i.x, now, dst + i.y, dep + 1);
    }
}

int calc(int now, int prv, int dst, int dep){
    int ret = 1e9+7;
    if(dst > k) return ret;
    if(chk[k-dst] < 1e9){
        ret = chk[k-dst] + dep;
    }
    for(auto i : g[now]){
        if(use[i.x] || i.x == prv) continue;
        ret = min(ret, calc(i.x, now, dst + i.y, dep + 1));
    }
    return ret;
}

int solve(int v){
    int cnt = getSize(v, -1);
    int cent = getCent(v, -1, cnt); use[cent] = 1;
    int ret = 1e9+7;
    for(auto i : init){
        chk[i] = 1e9+7;
    }
    init.clear();
    chk[0] = 0;

    for(auto i : g[cent]){
        if(use[i.x]) continue;
        ret = min(ret, calc(i.x, cent, i.y, 1));
        update(i.x, cent, i.y, 1);
    }
    for(auto i : g[cent]){
        if(use[i.x]) continue;
        ret = min(ret, solve(i.x));
    }
    return ret;
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N; k=K;
 
	for(int i=0;i<n-1;i++){
		g[H[i][0]].push_back({H[i][1],L[i]});
		g[H[i][1]].push_back({H[i][0],L[i]});
	}
    memset(chk, 0x3f, sizeof chk);
	int ans = solve(0);
 
	if(ans > 1e9) return -1;
	return ans;
}

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