Submission #595121

#	Time	Username	Problem	Language	Result	Execution time	Memory
595121		DAleksa	Race (IOI11_race)	C++17	9 / 100	3069 ms	21584 KiB

race

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

using namespace std;

struct edge {
    int v;
    int w;
};

#define MAX_N 500010
const int mxK = 1e6 + 10;

vector<edge> g[MAX_N];
int sz[MAX_N];
bool mark[MAX_N];
int cnt[2 * MAX_N + 10];
int mn[2 * MAX_N + 10];
int res = INT_MAX;

void get_sz(int u, int par) {
    sz[u] = 1;
    for(edge v : g[u]) {
        if(v.v == par) 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(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(w > k) return;
    mn[w] = INT_MAX;
    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(w > k) return;
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        if(cnt[k - w]) 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) {
    for(edge v : g[u]) {
        if(v.v == par || mark[v.v]) continue;
        if(sz[v.v] > n / 2) return find_centroid(v.v, u, n);
    }
    return u;
}

void solve(int u, int n, int k) {
    get_sz(u, 0);
    int centroid = find_centroid(u, 0, n);
    mark[centroid] = true;
    for(edge v : g[centroid]) {
        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]);
    for(edge v : g[centroid]) Remove(v.v, centroid, v.w, k);
    for(edge v : g[centroid]) {
        if(mark[v.v]) continue;
        solve(v.v, n, k);
    }
}

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] = INT_MAX;
    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