Submission #838865

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

race

// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

template<typename T>
string tostr(const T& value) {
    ostringstream oss;
    oss << value;
    return oss.str();
}

template<typename... Args>
string fstr(const string& format, Args... args) {
    string result = format;
    size_t pos = 0;
    size_t argIndex = 0;

    auto replaceArg = [&](const auto& arg) {
        pos = result.find("{}", pos);
        if (pos != string::npos) {
            result.replace(pos, 2, tostr(arg));
            ++argIndex;
        }
    };

    (replaceArg(args), ...);

    return result;
}


template<int SZ> struct Tree {
    int n;
    vector<pair<int,int>> adj[SZ];
    void init(int N) {
        n = N;
        for (int i = 0; i < n-1; i++) {
            int a, b, c; cin >> a >> b >> c;
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
        }
    }
};

const int maxn = 200000;

int n, k;
int sz[maxn], dpth[maxn], ldpth[maxn];
Tree<maxn> tree;
unordered_map<int,int> m[maxn];

int ans = INT_MAX;

int dfs(int nd, int par, int l) {
    sz[nd] = 1, dpth[nd] = dpth[par] + 1; ldpth[nd] = l;
    for (auto i : tree.adj[nd])
        if (i.first != par)
            sz[nd] += dfs(i.first, nd, l + i.second);
    return sz[nd];
}

inline int mget(int nd, int dist) {
    // dist to find = ldist[nd] + dist;
    dist += ldpth[nd];
    if (m[nd].find(dist) == m[nd].end()) return INT_MAX;
    return m[nd][dist];
}

inline void upd_min(int nd, int k, int v) {
    if (m[nd].find(k) == m[nd].end()) {m[nd][k] = v; return; }
    // cout << "Y " << nd << ' ' << k << ' ' << (m[nd].find(k) == m[nd].end()) << ' ' << m[nd][k] << ' ';
    m[nd][k] = min(m[nd][k], v);
    // cout << m[nd][k] << endl;
}

void msl(int nd, int par) {

    for (auto i : tree.adj[nd])
        if (i.first != par)
            msl(i.first, nd);

    int hch = -1, hb = -1;
    for (auto i : tree.adj[nd])
        if (i.first != par)
            if (hch == -1 || hb < sz[i.first])
                hch = i.first, hb = sz[i.first];
    // cout << "Z " << nd << ' ' << (hch == -1) << endl;
    if (hch == -1) {m[nd][ldpth[nd]] = dpth[nd];
    // cout << "---------" << endl << nd << endl;
    // cout << "X ";
    // for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
    // cout << endl;
    return;}
    // cout << "----" << endl;

    swap(m[nd], m[hch]);

    // cout << nd << endl;
    for (auto i : tree.adj[nd])
        if (i.first != par && i.first != hch)
            for (auto j : m[i.first]) {
                // cout << j.first << ' ' << j.second << endl;
                // (dist[i], dpth[i]) --> (dist[i] - dist[nd], dpth[i] - dpth[nd])
                int val = mget(nd, k - (j.first - ldpth[nd]));
                if (val != INT_MAX)
                    ans = min(ans, j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd]);
                // if (val != INT_MAX)
                //     cout << nd << ' ' << j.first << ' ' << j.second << ' ' << j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd] << endl;
                upd_min(nd, j.first, j.second);
            }

    // cout << nd << ' ' << mget(nd, k) - dpth[nd] << endl;
    // cout << "X ";
    // for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
    // cout << endl;
    ans = min(ans, mget(nd, k) - dpth[nd]);
    upd_min(nd, ldpth[nd], dpth[nd]);
}

void solve() {
    cin >> n >> k;
    tree.init(n);
    dfs(0, 0, 0);
    msl(0, 0);
    cout << ans << endl;
}

// #define LOCAL
// #define CODEFORCES
signed main() {
    #ifndef LOCAL
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    #endif
    #ifdef LOCAL
    freopen("main.in", "r", stdin);
    #endif
    int t; 
    #ifdef CODEFORCES
    cin >> t;
    #endif
    #ifndef CODEFORCES
    t=1;
    #endif
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cczo3zsX.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccapJDUW.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccapJDUW.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