Submission #595213

#	Time	Username	Problem	Language	Result	Execution time	Memory
595213		DAleksa	Race (IOI11_race)	C++17	9 / 100	215 ms	19984 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

#define int long long

struct edge {
    int v;
    int w;
};

const int MAX_N = 2e5 + 10;
const int mxK = 1e6 + 10;
const int inf = 1e18;

vector<edge> g[MAX_N];
int sz[MAX_N];
bool mark[MAX_N];
int cnt[mxK];
int mn[mxK];
int res = LLONG_MAX;

void get_sz(int u, int par) {
    if(mark[u]) return;
    sz[u] = 1;
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        get_sz(v.v, u);
        sz[u] += sz[v.v];
    }
}

void Add(int u, int par, int w, int k, int edges_count) {
    if(mark[u]) return;
    if(w > k) return;
    cnt[w]++;
    mn[w] = min(mn[w], edges_count);
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        Add(v.v, u, w + v.w, k, edges_count + 1);
    }
}

void Remove(int u, int par, int w, int k) {
    if(mark[u]) return;
    if(w > k) return;
    mn[w] = inf;
    cnt[w] = 0;
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        Remove(v.v, u, w + v.w, k);
    }
}

void dfs(int u, int par, int w, int k, int edges_count) {
    if(mark[u]) return;
    if(w >= k) return;
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        if(cnt[k - w] > 0) res = min(res, edges_count + mn[k - w]);
        dfs(v.v, u, w + v.w, k, edges_count + 1);
    }
}

int find_centroid(int u, int par, int n, int usize) {
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        if(sz[v.v] * 2 > usize) return find_centroid(v.v, u, n, usize);
    }
    return u;
}

void solve(int u, int n, int k) {
    get_sz(u, 0);
    int centroid = find_centroid(u, 0, n, sz[u]);
    mark[centroid] = true;
    for(edge v : g[centroid]) {
        if(mark[v.v]) continue;
        dfs(v.v, centroid, v.w, k, 1);
        Add(v.v, centroid, v.w, k, 1);
    }
    if(cnt[k] > 0) {
        res = min(res, mn[k]);
        assert(mn[k] > 0);
    }
    for(edge v : g[centroid]) {
        if(mark[v.v]) continue;
        Remove(v.v, centroid, v.w, k);
    }
    for(edge v : g[centroid]) {
        if(mark[v.v]) continue;
        solve(v.v, n, k);
    }
}

#undef int

int best_path(int n, int k, int h[][2], int l[]) {
    for(int i = 0; i < n - 1; i++) {
        g[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
        g[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
    }
    for(int i = 0; i < mxK; i++) mn[i] = inf;
    solve(1, n, k);
    int ret = res;
    if(ret == INT_MAX) return -1;
    return ret;
}

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