Submission #1076096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1076096	2024-08-26T11:06:57 Z	ducdev	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 2e5;
const int MAX_K = 1e6;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int n, k, currentCentroid;
int cnt[MAX_K + 5], sz[MAX_N + 5], root[MAX_N + 5];
int res = INF;
bool del[MAX_N + 5];
vector<ii> adj[MAX_N + 5];

void dfs(int u, int par) {
    sz[u] = 1;
    for (ii e : adj[u]) {
        int v = e.first;
        if (v == par || del[v]) continue;
        dfs(v, u);
        sz[u] += sz[v];
    };
};

int getCentroid(int u, int par, int n) {
    for (ii e : adj[u]) {
        int v = e.first;
        if (v == par || del[v]) continue;
        if (sz[v] * 2 > n)
            return getCentroid(v, u, n);
    };
    return u;
};

void update(int u, int par, bool updateResult, int sum, int d) {
    if (sum > k) return;
    if (updateResult) {
        root[u] = currentCentroid;
        res = min(res, d + cnt[k - sum]);
    } else {
        if (currentCentroid != root[u]) cnt[sum] = INF;
        cnt[sum] = min(cnt[sum], d);
    };

    for (ii e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == par || del[v]) continue;
        update(v, u, updateResult, sum + w, d + 1);
    };
};

void decompose(int u, int par) {
    dfs(u, par);

    int n = sz[u];
    int centroid = getCentroid(u, par, n);

    del[centroid] = true;
    root[centroid] = centroid;
    currentCentroid = centroid;

    for (ii e : adj[centroid]) {
        int v = e.first, w = e.second;
        if (del[v]) continue;
        update(v, centroid, true, w, 1);
        update(v, centroid, false, w, 1);
    };

    for (ii e : adj[centroid]) {
        int v = e.first;
        if (del[v]) continue;
        decompose(v, centroid);
    };
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        adj[u].push_back(ii(v, w));
        adj[v].push_back(ii(u, w));
    };

    for (int i = 1; i <= k; i++) cnt[i] = INF;
    cnt[0] = 0;

    decompose(1, 0);
    cout << (res == INF ? -1 : res) << '\n';
};

Compilation message

race.cpp: In function 'int main()':
race.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccYvkTcU.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQjsoXW.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccQjsoXW.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status