Submission #1184629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184629		LolkasMeep	Dreaming (IOI13_dreaming)	C++20	Compilation error	0 ms	0 KiB

dreaming

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

pair<int, int> createTree(int n, int* tree, bool* visited, vector<unordered_map<int, int>> &graph, pair<pair<int, int>, pair<int, int>>* depth, unordered_set<int> &nodes){
    visited[n] = true;

    nodes.insert(n);
    // depth[n].first = {d.first, dist};

    for(const pair<int, int> &child : graph[n]){
        if(visited[child.first]) continue;
        
        tree[child.first] = n;
        pair<int, int> d = createTree(child.first, tree, visited, graph, depth, nodes);
        int dist = d.second + child.second;
        // cout << "| " << n << ' ' << child.first << ' ' << dist << '\n';
        if(dist > depth[n].first.second){
            // cout << "Swapped: " << depth[n].first.first << ' ' << child.first << '\n';
            depth[n].second = make_pair(child.first, dist);
            swap(depth[n].second, depth[n].first);
        }else if(dist > depth[n].second.second){
            // cout << "Swapped: " << depth[n].second.first << ' ' << child.first << '\n';
            // cout << "??: " << depth[n].second.second << ' ' << dist << '\n';
            depth[n].second = make_pair(child.first, dist);
        }else{
            // cout << "didnt make it :(\n";
        }
    }

    return depth[n].first;
}

void dfsUPUP(int node, bool* visited, int* up, int* upup, int prev, vector<unordered_map<int, int>> &graph){
    visited[node] = node;

    for(const pair<int, int> &child : graph[node]){
        if(visited[child.first]) continue;
        dfsUPUP(child.first, visited, up, upup, max(up[child.first], child.second + prev), graph);
    }

    upup[node] = prev;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    bool visited[100005] = {false};
    int t = N-M-1;

    vector<int> radii(t+1);
    vector<int> diameter(t+1);

    vector<unordered_map<int, int>> graph(N);

    for(int i = 0; i <  M; i++){
        graph[A[i]][B[i]] = T[i];
        graph[B[i]][A[i]] = T[i];
    }

    int tree[100005] = {-1};
    pair<pair<int, int>, pair<int, int>> depth[100005];
    for(int i = 0; i < 100005; i++) depth[i] = {{-1,0}, {-1,0}};
    int up[100005] = {0};
    bool upupVisited[100005] = {false};
    int upup[100005] = {0};

    int index = -1;
    for(int root = 0; root < N; root++){
        if(visited[root]) continue;
        // cout << "tree\n";
        // cout << "root: " << root << '\n';
        unordered_set<int> nodes;    
        createTree(root, tree, visited, graph, depth, nodes);
        index++;

        // cout << "depth: ";
        // for(const int &node : nodes) cout << node << ":" << 
        //     depth[node].first.first << ',' << depth[node].first.second 
        //     << "(" << depth[node].second.first << ',' << depth[node].second.second << ' ';
        // cout << '\n';
        
        if(nodes.size() == 1){
            radii[index] = 0;
            diameter[index] = 0; 
        } 

        for(const int &node : nodes){
            if(tree[node] == -1) continue;

            if(depth[tree[node]].first.first == node){
                up[node] = depth[tree[node]].second.second + graph[node][tree[node]];
            }else{
                up[node] = depth[tree[node]].first.second + graph[node][tree[node]];
            }
        }

        // cout << "up: ";
        // for(const int &node : nodes) cout << node << ":" << up[node] << ' ';
        // cout << '\n';

        dfsUPUP(root, upupVisited, up, upup, 0, graph);
        
        int radius = INT_MAX;
        int dm = 0;
        for(const int &node : nodes){
            radius = min(radius, max(upup[node], depth[node].first.second));
            dm = max(dm, max(upup[node], depth[node].first.second));
        }
        
        radii[index] = radius;
        diameter[index] = dm;
    }

    // for(int i = 0; i < t+1; i++){
    //     cout << radii[i] << ' ';
    // }
    // cout << '\n';

    // for(int i = 0; i < t+1; i++){
    //     cout << diameter[i] << ' ';
    // }
    // cout << '\n';

    int mxDist = 0;
    int mxRad = -1;
    int mxRad1 = -1;
    for(int i = 0; i < t+1; i++) mxDist = max(mxDist, diameter[i]);
    for(int i = 1; i < t+1; i++) {
        mxDist = max(mxDist, radii[0] + L + radii[i]);
        if(radii[i] > mxRad){
            mxRad1 = radii[i];
            swap(mxRad1, mxRad);
        }else if(radii[i] > mxRad1) mxRad1 = radii[i];
    }
    if(t+1 >= 3){
        mxDist = max(mxDist, mxRad1 + mxRad + L * 2);
    }

    return mxDist;
}

// int A[] = {0, 8, 2, 5, 5, 1, 1, 10};
// int B[] = {8, 2, 7, 11, 1, 3, 9, 6};
// int T[] = {4, 2, 4, 3, 7, 1, 5, 3};
// int main(){
//     int ans = travelTime(12, 8, 2, A, B, T);
//     cout << ans << '\n';
//     return 0;
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGFoQbC.o: in function `main':
grader.c:(.text.startup+0xc4): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status