Submission #674954

#	Time	Username	Problem	Language	Result	Execution time	Memory
674954		tox1c_kid	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include "bits/stdc++.h"
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>

/*
 ⠄⠄⠄⢰⣧⣼⣯⠄⣸⣠⣶⣶⣦⣾⠄⠄⠄⠄⡀⠄⢀⣿⣿⠄⠄⠄⢸⡇⠄⠄
⠄⠄⠄⣾⣿⠿⠿⠶⠿⢿⣿⣿⣿⣿⣦⣤⣄⢀⡅⢠⣾⣛⡉⠄⠄⠄⠸⢀⣿⠄
⠄⠄⢀⡋⣡⣴⣶⣶⡀⠄⠄⠙⢿⣿⣿⣿⣿⣿⣴⣿⣿⣿⢃⣤⣄⣀⣥⣿⣿⠄
⠄⠄⢸⣇⠻⣿⣿⣿⣧⣀⢀⣠⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⣿⣿⣿⠄
⠄⢀⢸⣿⣷⣤⣤⣤⣬⣙⣛⢿⣿⣿⣿⣿⣿⣿⡿⣿⣿⡍⠄⠄⢀⣤⣄⠉⠋⣰
⠄⣼⣖⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⢇⣿⣿⡷⠶⠶⢿⣿⣿⠇⢀⣤
⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⣿⣿⣿⣿⣿⣿⣷⣶⣥⣴⣿⡗
⢀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄
⢸⣿⣦⣌⣛⣻⣿⣿⣧⠙⠛⠛⡭⠅⠒⠦⠭⣭⡻⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠄
⠘⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠄⠹⠈⢋⣽⣿⣿⣿⣿⣵⣾⠃⠄
⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⠄⣴⣿⣶⣄⠄⣴⣶⠄⢀⣾⣿⣿⣿⣿⣿⣿⠃⠄⠄
⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⠄⣿⣿⡀⣾⣿⣿⣿⣿⣛⠛⠁⠄⠄⠄
⠄⠄⠄⠄⠈⠛⢿⣿⣿⣿⠁⠞⢿⣿⣿⡄⢿⣿⡇⣸⣿⣿⠿⠛⠁⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠉⠻⣿⣿⣾⣦⡙⠻⣷⣾⣿⠃⠿⠋⠁⠄⠄⠄⠄⠄⢀⣠⣴
⣿⣿⣿⣶⣶⣮⣥⣒⠲⢮⣝⡿⣿⣿⡆⣿⡿⠃⠄⠄⠄⠄⠄⠄⠄⣠⣴⣿⣿⣿
 */

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define all(x) (x).begin(), (x).end()
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#ifdef CLOWN
#include "trash.h"
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
#else
#define dbg(...);
#endif

int test = 0;

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

#define int ll

vector<vector<pair<int, int>>> g;
vector<int> dp, used;
int ans = 1e18;

void dfs(int u, int p) {
    used[u] = 1;
    for (auto [v, c] : g[u]) {
        if (v ^ p) {
            dfs(v, u);
            dp[u] = max(dp[u], dp[v] + c);
        }
    }
}

void root(int u, int p, int prev_up = 0) {
    multiset<int> s;
    int val = 0;
    for (auto [v, c] : g[u]) {
        if (v ^ p) {
            s.insert(dp[v] + c);
        } else {
            val = c;
        }
    }
    s.insert(prev_up + val);
    ans = min(ans, *(s.rbegin()));
    dbg(u, s)
    for (auto [v, c] : g[u]) {
        if (v ^ p) {
            s.erase(s.find(dp[v] + c));
            root(v, u, (*s.rbegin()));
            s.insert(dp[v] + c);
        }
    }
}

void solve() {
    int n, m, l;
    cin >> n >> m >> l;
    g.resize(n + 1);
    dp.resize(n + 1);
    used.resize(n + 1);
    for (int i = 1; i <= m; i++)  {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    if (n == 1) {
        cout << "0\n";
        return;
    }
    int root = 0;
    dfs(root, -1);
    ans = dp[root];
    ::root(root, -1);
    root = -1;
    for (int i =  0; i < n; i++) {
        if (!used[i]) {
            root = i;
            break;
        }
    }
    if (root == -1) assert(false);
    dbg("")
    int L = ans;
    dfs(root, -1);
    ans = dp[root];
    ::root(root, -1);
    cout << ans + L + l << "\n";
}

int32_t main() {
#ifdef CLOWN
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    fastio();
    if (test) cin >> t;
    while (t--) { solve(); }
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccrVplKl.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3JokZk.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc3JokZk.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status