Submission #1285631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285631		sundryyarn	꿈 (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

// #include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
typedef pair<int, int> pi;
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    vector<vector<pi>> g(N);
    for (int i = 0; i < M; i ++)
    {
        g[A[i]].push_back(make_pair(T[i], B[i]));
        g[B[i]].push_back(make_pair(T[i], A[i]));
    }

    vector<bool> visited(N, false);
    const auto getFurthest = [&](const int start, vector<int>& dist) -> int
    {
        int result = start;
        queue<int> q({start});
        visited[start] = true;
        while (! q.empty())
        {
            const int u = q.front();
            q.pop();
            for (const pi& p : g[u])
                if (! visited[p.second])
                {
                    q.push(p.second);
                    visited[p.second] = true;
                    dist[p.second] = dist[u] + p.first;
                    // cout << u << " -> " << p.second << ", dist " << dist[u] << " -> " << dist[p.second] << endl;
                    if (dist[result] < dist[p.second])
                        result = p.second;
                }
        }
        return result;
    };
    const auto getMinDist = [&](const int start, const vector<int>& du, const vector<int>& dv) -> int
    {
        int result = max(du[start], dv[start]);
        queue<int> q({start});
        visited[start] = true;
        while (! q.empty())
        {
            const int u = q.front();
            q.pop();
            for (const pi& p : g[u])
                if (! visited[p.second])
                {
                    q.push(p.second);
                    visited[p.second] = true;
                    result = min(result, max(du[p.second], dv[p.second]));
                }
        }
        return result;
    };
    vector<int> tree_u, tree_v, d_(N, 0), du(N, 0), dv(N, 0);
    for (int i = 0; i < N; i ++)
        if (! visited[i])
            tree_u.push_back(getFurthest(i, d_));
    
    // cout << "distances from u:\n";
    visited = vector<bool>(N, 0);
    for (const int& u : tree_u)
        tree_v.push_back(getFurthest(u, du));

    
    // cout << "distances from v:\n";
    visited = vector<bool>(N, 0);
    for (const int& v : tree_v)
        getFurthest(v, dv);
    
    vector<int> tree;
    visited = vector<bool>(N, 0);
    for (const int& u : tree_u)
        tree.push_back(getMinDist(u, du, dv));
    sort(tree.rbegin(), tree.rend());

    int result = *max_element(du.begin(), du.end());
    if (tree.size() > 1) result = max(result, tree[0] + tree[1] + L);
    if (tree.size() > 2) result = max(result, tree[1] + tree[2] + 2 * L);
    return result;
}
// int main()
// {
//     freopen("dreaming.in", "r", stdin);
//     freopen("dreaming.out", "w", stdout);
//     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/ccZvBGNX.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status