Submission #1326777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326777		matrix27	Dreaming (IOI13_dreaming)	C++20	14 / 100	1095 ms	22692 KiB

dreaming

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

using namespace std;
using ll = long long;

pair<ll, ll> findFurthest(unordered_map<ll, vector<pair<ll, ll>>>& g, ll node, ll parent, bool findAncestory, vector<ll>& ancestor) {
    ll furthestNode = node;
    if (findAncestory) ancestor[node] = parent;
    ll maxDistance = 0;
    for (pair<ll, ll> next : g[node]) {
        ll nextNode = next.first;
        ll 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<ll, vector<pair<ll, ll>>>& g, ll node, ll parent, vector<ll>& visited) {
    visited[node] = 1;
    for (pair<ll, ll> next : g[node]) {
        ll nextNode = next.first;
        if (nextNode != parent && !visited[nextNode]) markCC(g, nextNode, node, visited);
    }
}

void solveCC(unordered_map<ll, vector<pair<ll, ll>>>& g, ll node, vector<ll>& diameters, vector<ll>& eccentricities, vector<ll>& visited, ll N) {
    markCC(g, node, -1, visited);
    vector<ll> ancestors(N, -1);
    ll nodeA = findFurthest(g, node, -1, 0, ancestors).first;
    auto [nodeB, diameter] = findFurthest(g, nodeA, -1, 1, ancestors);
    diameters.push_back(diameter);
    ll currentNode = nodeB;
    ll currentDistance = 0;
    while(ancestors[currentNode] != -1) {
        ll parent = ancestors[currentNode];
        for (pair<ll, ll> 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;
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    unordered_map<ll, vector<pair<ll, ll>>> g;
    for (ll i = 0; i < M; i++) {
        ll a = A[i], b = B[i], c = T[i];
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector<ll> visited(N, 0);
    vector<ll> diameters;
    vector<ll> eccentricities;
    ll maxDiameter = 0;
    for (ll 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;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23