Submission #544311

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

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MAX = 1e5 + 10;

int ans;
vector <pair <int, int>> adj[MAX];
pair <int, int> ma[MAX][2];
bool visited[MAX];

template <typename T>
void upd(T *ma, T x, int n) {
    for(int i = 0; i < n; i++) {
        if(ma[i] < x) {
            swap(ma[i], x);
        }
    }
}

void dfs(int u) {
    for(auto [v, w] : adj[u]) {
        if(visited[v] == true) {
            continue;
        }
        visited[v] = true;

        dfs(v);
        upd(ma[u], make_pair(ma[v][0].first + w, v), 2);
    }
    ans = max(ans, ma[u][0].first + ma[u][1].first);
}

int dfs2(int u, int pw) {
    int res = max(ma[u][0].first, pw);
    for(auto [v, w] : adj[u]) {
        if(visited[v] == true) {
            continue;
        }
        visited[v] = true;

        int nw = pw;
        if(ma[u][0].second == v) {
            nw = max(nw, ma[u][1].first);
        }
        else {
            nw = max(nw, ma[u][0].first);
        }

        res = min(res, dfs2(v, nw + w));
    }
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++) {
        A[i]++, B[i]++;
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }

    for(int i = 1; i <= N; i++) {
        ma[i][0] = make_pair(0, -1);
        ma[i][1] = make_pair(0, -1);
    }
    for(int i = 1; i <= N; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            dfs(i);
        }
    }

    for(int i = 1; i <= N; i++) {
        visited[i] = false;
    }
    
    vector <int> max_dist;
    for(int i = 1; i <= N; i++) {
        if(visited[i] == false) {
            visited[i] = true;
            max_dist.push_back(dfs2(i, 0));
        }
    }

    sort(max_dist.rbegin(), max_dist.rend());
    if(max_dist.size() > 1) {
        ans = max(ans, max_dist[0] + max_dist[1] + L);
    }
    if(max_dist.size() > 2) {
        ans = max(ans, max_dist[1] + max_dist[2] + 2 * L);
    }
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, M, L;
    cin >> N >> M >> L;
    int A[M], B[M], T[M];
    for(int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> T[i];
    }
    cout << travelTime(N, M, L, A, B, T);
    return 0;
}

Compilation message (stderr)

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