Submission #1115376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115376	2024-11-20T12:01:18 Z	gustavo_d	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

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;
}
 
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, int op);
    }
}
 
int ans = 1e8;
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);
}

Compilation message

race.cpp: In function 'void dfs_dist(int, int, int, int, int)':
race.cpp:39:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
   39 |         ans = min(ans, dists[k-dist] + depth);
      |         ^~~
      |         abs
race.cpp:45:45: error: expected primary-expression before 'int'
   45 |         dfs_dist(viz, v, dist + w, depth+1, int op);
      |                                             ^~~