Submission #1243827

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

dreaming

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

const int mxN = 1e5 + 100;
const int INF = 2e9;

vector<pair<int,int>> adj[mxN];
int down_dp[mxN], up_dp[mxN];
bool vis[mxN];
int cmax = 0;

void dfs(int u, int p){
    vis[u] = 1;
   // cout << u << " ";
    for(auto it : adj[u]){
        if(it.first ^ p){
            dfs(it.first, u);
            down_dp[u] = max(down_dp[u], down_dp[it.first] + it.second);
        }
    }
}

void reroot(int u, int p){
    pair<int, int> mx1, mx2;
    mx1.first = mx2.first = mx2.second = -1;

    for(auto it : adj[u]){
        if(it.first ^ p){
            if(mx1.first == -1){
                mx1.first = it.first;
                mx1.second = down_dp[it.first] + it.second;
            }else if(down_dp[it.first] + it.second >= mx1.second){
                swap(mx1, mx2);
                mx1.first = it.first;
                mx1.second = down_dp[it.first] + it.second;
            }else if(down_dp[it.first] + it.second > mx2.second){
                mx2.first = it.first;
                mx2.second = down_dp[it.first] + it.second;
            }
        }
    }

    for(auto it : adj[u]){
        if(it.first ^ p){
            if(it.first == mx1.first){
                if(mx2.first != -1){
                    up_dp[it.first] = mx2.second + it.second;
                }
            }else if(mx1.first != 1){
                up_dp[it.first] = mx1.second + it.second;
            }
            up_dp[it.first] = max(up_dp[it.first], up_dp[u] + it.second);
            reroot(it.first, u);
        }
    }
    cmax = min(cmax, max(up_dp[u], down_dp[u]));
}

int main(){
    int n, m, l, u, v, w;
    cin >> n >> m >> l;
    for(int i = 0; i < m; ++i){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<int> tokens;
    for(int i = 0; i < n; ++i){
        if(!vis[i]){
            cmax = INF;
        //    cout << "started visiting:- ";
            dfs(i, -1);
            reroot(i, -1);
          //  cout << "ended visiting\n";
            tokens.push_back(cmax);
           // cout << i << " " << cmax << endl;
        }
    }

    sort(tokens.begin(), tokens.end());

  //  cout << "2 updp : " << up_dp[2] << " downdp: " << down_dp[2] << endl;

    if(tokens.size() == 1){
        cout << tokens.back() << "\n";
    }else{
        cout << tokens[tokens.size() - 2] + l + tokens.back() << "\n";
    }

    return 0;
}

Compilation message (stderr)

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