Submission #1326770

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

dreaming

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include "dreaming.h"

using namespace std;
using ll = long long;

pair<int, ll> findFurthest(unordered_map<int, vector<pair<int, int>>>& g, int node, int parent, bool findAncestory, vector<int>& ancestor) {
    int furthestNode = node;
    if (findAncestory) ancestor[node] = parent;
    ll maxDistance = 0;
    for (pair<int, int> next : g[node]) {
        int nextNode = next.first;
        int weight = next.second;
        if (nextNode != parent) {
            auto [candidateNode, candidateDistance] = findFurthest(g, nextNode, node, findAncestory, ancestor);
            candidateDistance += weight;
            if (candidateDistance > maxDistance) {
                maxDistance = candidateDistance;
                furthestNode = candidateNode;
            }
        }
    }
    return {furthestNode, maxDistance};
}

void markCC(unordered_map<int, vector<pair<int, int>>>& g, int node, int parent, vector<int>& visited) {
    visited[node] = 1;
    for (pair<int, int> next : g[node]) {
        int nextNode = next.first;
        if (nextNode != parent && !visited[nextNode]) markCC(g, nextNode, node, visited);
    }
}

void solveCC(unordered_map<int, vector<pair<int, int>>>& g, int node, vector<ll>& diameters, vector<ll>& eccentricities, vector<int>& visited, int N) {
    markCC(g, node, -1, visited);
    vector<int> ancestors(N, -1);
    int nodeA = findFurthest(g, node, -1, 0, ancestors).first;
    auto [nodeB, diameter] = findFurthest(g, nodeA, -1, 1, ancestors);
    diameters.push_back(diameter);
    int currentNode = nodeB;
    ll currentDistance = 0;
    while(ancestors[currentNode] != -1) {
        int parent = ancestors[currentNode];
        for (pair<int, int> next : g[currentNode]) {
            if (next.first == parent) {
                if ((currentDistance + next.second) * 2 == diameter) {eccentricities.push_back(currentDistance + next.second); return;}
                else if ((currentDistance + next.second) * 2 > diameter) {
                    if (max(currentDistance, diameter - currentDistance) <= max(currentDistance + next.second, diameter - currentDistance - next.second)) eccentricities.push_back(max(currentDistance, diameter - currentDistance));
                    else eccentricities.push_back(max(currentDistance + next.second, diameter - currentDistance - next.second));
                    return;
                }
                currentDistance += next.second;
                break;
            }
        }
        currentNode = parent;
    }
}

ll travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    unordered_map<int, vector<pair<int, int>>> g;
    for (int i = 0; i < M; i++) {
        int a = A[i], b = B[i], c = T[i];
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector<int> visited(N, 0);
    vector<ll> diameters;
    vector<ll> eccentricities;
    ll maxDiameter = 0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) solveCC(g, i, diameters, eccentricities, visited, N);
        maxDiameter = max(maxDiameter, diameters.back());
    }
    sort(eccentricities.begin(), eccentricities.end(), greater<ll>());
    // cout << maxDiameter << '\n';
    // cout << "ECCENTRICITIES: " << eccentricities[0] << " " << eccentricities[1] << " " << eccentricities[2] << '\n';
    ll ans = maxDiameter;
    if (eccentricities.size() >= 2) ans = max(ans, eccentricities[0] + eccentricities[1] + L);
    if (eccentricities.size() >= 3) ans = max(ans, eccentricities[1] + eccentricities[2] + 2LL*L);
    return ans;
}

Compilation message (stderr)

dreaming.cpp:63:4: error: ambiguating new declaration of 'll travelTime(int, int, int, int*, int*, int*)'
   63 | ll travelTime(int N, int M, int L, int A[], int B[], int T[]) {
      |    ^~~~~~~~~~
In file included from dreaming.cpp:5:
dreaming.h:8:5: note: old declaration 'int travelTime(int, int, int, int*, int*, int*)'
    8 | int travelTime(int N, int M, int L, int A[], int B[], int T[]);
      |     ^~~~~~~~~~