Submission #1114997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114997		gustavo_d	Race (IOI11_race)	C++17	21 / 100	3069 ms	186792 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")

const int MAXN = 2e5;
const int MAXV = 1e6+1;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];
bool in[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 or in[viz]) 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);
}

vector<int> sub_mn_depth(MAXV, 1e8);
vector<pair<int, int>> dists[MAXV];
vector<int> sub_dists;
void get_dist(int v, int pai, int dist, int depth) {
    if (dist > k) return;
    sub_mn_depth[dist] = min(sub_mn_depth[dist], depth);
    sub_dists.push_back(dist);
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        get_dist(viz, v, dist + w, depth+1);
    }
}

int ans = 1e8;
void decomp(int v) {
    int centroid = find_centroid(v, -1);
    in[centroid] = true;
    vector<int> all_dists;
    // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        get_dist(viz, centroid, w, 1);
        for (int d : sub_dists) {
            dists[d].push_back({sub_mn_depth[d], viz});
            sub_mn_depth[d] = 1e8;
            all_dists.push_back(d);
        }
        sub_dists.clear();
    }
    for (int d : all_dists) {
        sort(dists[d].begin(), dists[d].end());
    }
    if (!dists[k].empty()) ans = min(ans, dists[k][0].first);
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        get_dist(viz, centroid, w, 1);
        for (int d : sub_dists) {
            for (int i=0; d <= k and 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 + sub_mn_depth[d]);
            }
            sub_mn_depth[d] = 1e8;
        }
        sub_dists.clear();
    }
    for (int d : all_dists) dists[d].clear();
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        decomp(viz);
    }
    in[centroid] = false;
}

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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57