Submission #639842

#	Time	Username	Problem	Language	Result	Execution time	Memory
639842		classic	Race (IOI11_race)	C++14	9 / 100	3079 ms	43396 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

vector<pair<int, int>> adj[N];
int sz[N];
bool vis[N];
int res;
map<int, int> mn;
vector<pair<int, int>> cand;

int dfsSz(int u, int p) {
    sz[u] = 1;
    for (pair<int, int> v : adj[u]) {
        if (v.first != p && !vis[v.first]) {
            sz[v.first] += dfsSz(v.first, u);
        }
    }
    return sz[u];
}

int centroid(int u, int p, int siz) {
    for (pair<int, int> v : adj[u]) {
        if (v.first != p && !vis[v.first] > siz / 2) {
            return centroid(v.first, u, siz);
        }
    }
    return u;
}

void dfs(int u, int p, int len, int d) {
    cand.emplace_back(len, d);
    for (pair<int, int> v : adj[u]) {
        if (v.first != p && !vis[v.first]) {
            dfs(v.first, u, len + v.second, d + 1);
        }
    }
}

void build(int u, int k) {
    dfsSz(u, -1);
    int c = centroid(u, -1, sz[u]);
    mn[0] = 0;
    for (pair<int, int> v : adj[c]) {
        if (!vis[v.first]) {
            dfs(v.first, c, v.second, 1);
            for (pair<int, int> x : cand) {
                int len = x.first;
                int d = x.second;
                if (mn.find(k - len) != mn.end()) {
                    res = min(res, mn[k - len] + d);
                }
            }
            for (pair<int, int> x : cand) {
                if (mn.find(x.first) == mn.end()) {
                    mn[x.first] = x.second;
                } else {
                    mn[x.first] = min(mn[x.first], x.second);
                }
            }
            mn.clear();
        }
    }
    mn.clear();
    vis[c] = true;
    for (pair<int, int> v : adj[c]) {
        if (!vis[v.first]) {
            build(v.first, k);
        }
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    for (int i = 0; i < n - 1; i++) {
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    res = 1e9;
    build(1, k);
    return (res == 1e9 ? -1 : res);
}

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