답안 #456259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
456259 2021-08-06T09:54:03 Z khoabright 꿈 (IOI13_dreaming) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define mp                     make_pair
#define pb                     push_back
#define ff                     first
#define ss                     second
#define all(x)                x.begin(), x.end()
#define testBit(n, bit) ((n >> bit) & 1)
#define flipBit(n, bit) (n ^ (1ll << bit))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
const int inf = 1e9;

vector<pii> g[N];
int d[N], pa[N], vst[N];
int n;
pii mx;
int ans = 0;

void dfs(int u, int p) {
    vst[u] = 1;
    mx = max(mx, {d[u], u});
    pa[u] = p;
    for (auto [v, w] : g[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
    }
}

int center(int x) {
    mx = {-1, -1};
    dfs(x, -1);
    int X = mx.ss;
    d[X] = 0;

    mx = {-1, -1};
    dfs(X, -1);
    int Y = mx.ss;

    ans = max(ans, mx.ff);

    mx = {inf, inf};
    int y = Y;
    while (y != pa[X]) {
        mx = min(mx, {max(d[y], d[Y] - d[y]), y});
        y = pa[y];
    }

    return mx.ff;
}

int solve() {
    int m, l; cin >> n >> m >> l;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> s;

    for (int i = 0; i < n; ++i) {
        if (!vst[i]) s.push_back(center(i));
    }

    sort(s.rbegin(), s.rend());

    if (s.size() > 1) ans = max(ans, s[0] + s[1] + l);
    if (s.size() > 2) ans = max(ans, s[1] + s[2] + 2 * l);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cout << solve();
}

Compilation message

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