Submission #964354

#	Time	Username	Problem	Language	Result	Execution time	Memory
964354		vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

#ifdef DEBUG
    #include <debug.hpp>
#else
    #define debug(...) 42
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

void fast_io();
void file_io(const string&);

struct Solution {
    int n, k; 
    int ans = 1e9;
    vector<vector<pair<int, int>>> g;
    vector<int> sz, used; 

    Solution() {
        cin >> n >> k;
        g.assign(n, {});
        sz.assign(n, 0);
        used.assign(n, 0);
    
        int u, v, w;
        for (int i = 0; i < n - 1; ++i) {
            cin >> u >> v >> w;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }

    int find_sz(int v, int p) {
        sz[v] = 1;
        for (auto [to, w] : g[v]) {
            if (used[to] || to == p) continue;
            sz[v] += find_sz(to, v);
        }
        return sz[v];
    }

    int centr(int v, int p, int cn) {
        bool flag = 1;
        while (flag) {
            flag = 0;
            for (auto [to, w] : g[v]) {
                if (used[to] || to == p) continue;
                if (sz[to] > cn / 2) {
                    p = v;
                    v = to;
                    flag = 1;
                    break;
                }
            }
        }
        return v;
    }
    
    void dfs(int v, int p, int d, int l, vector<pair<int, int>> &t) {
        t.emplace_back(d, l);
        for (auto [to, w] : g[v]) {
            if (used[to] || to == p) continue;
            dfs(to, v, d + w, l + 1, t);
        }
    } 

    void root_solve(int v, int vn) {
        unordered_map<int, int> d;
        d.reserve(vn);
        d[0] = 1;
        for (auto [to, w] : g[v]) {
            if (used[to]) continue;
            vector<pair<int, int>> t;
            t.reserve(sz[to]);
            dfs(to, v, w, 1, t);

            for (auto [x, y] : t) {
                if (k >= x && d[k - x] != 0) {
                    ans = min(ans, y + d[k - x] - 1);
                }
            }
            for (auto [x, y] : t) {
                if (d[x] == 0 || d[x] > y + 1) {
                    d[x] = y + 1;
                }
            }
        }
    }

    void decomp(int v) {
        int cn = find_sz(v, v);
        int c = centr(v, v, cn); 
        used[c] = 1;
        root_solve(c, cn);
        for (auto [to, w] : g[c]) {
            if (used[to]) continue;
            decomp(to);
        }
    }

    void solve() {
        decomp(0);
        cout << (ans == 1e9 ? -1 : ans) << "\n";
    }
};

int main() {
    fast_io();
    int t = 1; // cin >> t;
    for (int i = 1; i <= t; ++i) {
        Solution sol;
        sol.solve();
    }
}

void file_io(const string& name) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
}

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

Compilation message (stderr)

race.cpp: In function 'void file_io(const string&)':
race.cpp:121:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccS8tdtr.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccOGDMp.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cccOGDMp.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