Submission #1114942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114942		gustavo_d	Race (IOI11_race)	C++17	0 / 100	458 ms	262144 KiB

race

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

const int MAXN = 2e5;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];

int n, k;

void dfs(int v) {
    vis[v] = true; sz[v] = 1;
    for (auto& [viz, w] : adj[v]) {
        if (vis[viz]) continue;
        dfs(viz);
        sz[v] += sz[viz];
    }
}

int find_centroid(int v, int pai) {
    // cout << "buscando centroid " << v << endl;
    pair<int, int> mx = {v, 0};
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai) continue;
        if (mx.second < sz[viz]) mx = {viz, sz[viz]};
    }
    if (mx.second <= n / 2) {
        // cout << "é" << v <<endl;
        return v;
    }
    return find_centroid(mx.first, v);
}

map<int, int> sub_dist;
void get_dist(int v, int pai, int dist, int depth) {
    if (sub_dist.count(dist) == 0) sub_dist[dist] = depth;
    else sub_dist[dist] = min(sub_dist[dist], depth);
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai) continue;
        get_dist(viz, v, dist + w, depth+1);
    }
}

int ans = 1e8;
void decomp(int v, int last_centroid=-1) {
    int centroid = find_centroid(v, last_centroid);
    // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
    map<int, vector<pair<int, int>>> dists;
    for (auto& [viz, w] : adj[centroid]) {
        if (viz == last_centroid) continue;
        decomp(viz, centroid);
        get_dist(viz, centroid, w, 1);
        for (auto& [d, depth] : sub_dist) {
            dists[d].push_back({depth, viz});
        }
        sub_dist.clear();
    }
    for (auto it = dists.begin(); it != dists.end(); it++) {
        sort((it->second).begin(), (it->second).end());
    }
    if (!dists[k].empty()) ans = min(ans, dists[k][0].first);
    for (auto& [viz, w] : adj[centroid]) {
        if (viz == last_centroid) continue;
        get_dist(viz, centroid, w, 1);
        for (auto& [d, depth] : sub_dist) {
            for (int i=0; i<min(2, (int)dists[k-d].size()); i++) {
                if (dists[k-d][i].second == viz) continue;
                ans = min(ans, dists[k-d][i].first + depth);
            }
        }
        sub_dist.clear();
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for (int i=0; i<N-1; i++) {
        int u = H[i][0], v = H[i][1];
        int w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(0);
    decomp(0);

    return (ans == (int)1e8 ? -1 : ans);
}

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