제출 #1207825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207825		orcslop	꿈 (IOI13_dreaming)	C++20	59 / 100	1095 ms	9548 KiB

dreaming

#include <bits/stdc++.h>
#if __has_include("dreaming.h")
#include "dreaming.h"
#endif
using namespace std;
using ll = long long; 
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#define dbgn(...) 0
#endif

const int INF = 1e9; 

// Assuming the function signature from the problem
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for(int i = 0; i < m; i++){
        adj[a[i]].push_back({b[i], t[i]});
        adj[b[i]].push_back({a[i], t[i]});
    }

    const int INF = 1e9;
    std::vector<int> cc_radii;    // Renamed for clarity, stores radius of each component
    std::vector<int> cc_diameters; // ADDED: Stores diameter of each component

    auto dijkstra = [&](int start_node) {
        std::vector<int> dist(n, INF);
        if (start_node >= 0 && start_node < n) {
            dist[start_node] = 0;
            std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
            pq.push({0, start_node});
            while (!pq.empty()) {
                int d = pq.top().first;
                int u = pq.top().second;
                pq.pop();
                if (d > dist[u]) continue;
                for (auto& edge : adj[u]) {
                    int v = edge.first;
                    int weight = edge.second;
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.push({dist[v], v});
                    }
                }
            }
        }
        return dist;
    };

    std::vector<bool> vis(n, false);
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            std::vector<int> ccn;
            std::queue<int> q;
            q.push(i);
            vis[i] = true;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                ccn.push_back(u);
                for (auto& edge : adj[u]) {
                    int v = edge.first;
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
            if (ccn.size() <= 1) {
                cc_radii.push_back(0);
                cc_diameters.push_back(0); // Also add 0 for diameter
                continue;
            }

            // Find one endpoint of a diameter
            std::vector<int> st_dist = dijkstra(i);
            int endpoint_a = -1;
            int max_dist = -1;
            for (int node : ccn) {
                if (st_dist[node] != INF && st_dist[node] > max_dist) {
                    max_dist = st_dist[node];
                    endpoint_a = node;
                }
            }

            // Find the other endpoint and the component's diameter
            std::vector<int> a_dist = dijkstra(endpoint_a);
            int endpoint_b = -1;
            int component_diameter = -1; // This is the diameter value
            for (int node : ccn) {
                if (a_dist[node] != INF && a_dist[node] > component_diameter) {
                    component_diameter = a_dist[node];
                    endpoint_b = node;
                }
            }
            cc_diameters.push_back(component_diameter); // FIX: Store the diameter

            // Find the component's radius
            std::vector<int> b_dist = dijkstra(endpoint_b);
            int component_radius = INF; // This is the radius value
            for (int node : ccn) {
                int e = std::max(a_dist[node], b_dist[node]);
                if (e < component_radius) {
                    component_radius = e;
                }
            }
            cc_radii.push_back(component_radius);
        }
    }

    // --- Final Calculation ---
    int ans = 0;
    // Candidate 1: The largest diameter of any original component
    if (!cc_diameters.empty()) {
        ans = *std::max_element(cc_diameters.begin(), cc_diameters.end());
    }
    
    // Sort radii to easily find the largest ones
    std::sort(cc_radii.begin(), cc_radii.end(), std::greater<int>());

    // Candidate 2: Longest path spanning two components
    if (cc_radii.size() >= 2) {
        ans = std::max(ans, cc_radii[0] + cc_radii[1] + l);
    }
    
    // Candidate 3: Longest path spanning three components
    if (cc_radii.size() >= 3) {
        ans = std::max(ans, cc_radii[1] + cc_radii[2] + 2 * l);
    }
    
    return ans;
}

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