Submission #1115377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115377		gustavo_d	Race (IOI11_race)	C++17	21 / 100	3055 ms	20876 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, int pai) {
    sz[v] = 1;
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        dfs(viz, v);
        sz[v] += sz[viz];
    }
}

int find_centroid(int v, int pai, int qty) {
    // cout << "buscando centroid " << v << endl;
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        if (sz[viz] > qty / 2) find_centroid(viz, v, qty);
    }
    // cout << "é" << v <<endl;
    return v;
}

int ans = 1e8;
vector<int> dists(MAXV, 1e8);
// op = 1 => preenche, -1 => apaga, 0 => pega resposta
void dfs_dist(int v, int pai, int dist, int depth, int op) {
    if (dist > k) return;
    if (op == 0)
        ans = min(ans, dists[k-dist] + depth);
    else if (op == 1)
        dists[dist] = min(dists[dist], depth);
    else dists[dist] = 1e8;
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        dfs_dist(viz, v, dist + w, depth+1, op);
    }
}
 
void decomp(int v) {
    dfs(v, -1);
    int centroid = find_centroid(v, -1, sz[v]);
    in[centroid] = true;
    // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        dfs_dist(viz, centroid, w, 1, 0);  // resposta considera prefixo subárvores
        dfs_dist(viz, centroid, w, 1, 1);
    }
    ans = min(ans, dists[k]);
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        dfs_dist(viz, centroid, w, 1, -1);
    }
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        decomp(viz);
    }
}
 
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});
    }
 
    decomp(0);
 
    return (ans == (int)1e8 ? -1 : ans);
}

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