oj.uz

Submission #160644

# Submission time Handle Problem Language Result Execution time Memory
160644 2019-10-29T05:04:02 Z jhnah917 Race (IOI11_race) C++14
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include "race.h"
#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]});
	}
 
	int ans = solve(0);
 
	if(ans > 1e9) return -1;
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -