제출 #1180411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180411		burgerguy	Dreaming (IOI13_dreaming)	C++20	59 / 100	1095 ms	34820 KiB

dreaming

#include <bits/stdc++.h>
#include"dreaming.h"

using namespace std;
using ll = long long;

pair<ll,ll> getRadiusNode(ll initialNode, vector<vector<pair<ll,ll>>> adj, vector<bool>& vis) {
    map<ll,ll> dist1, dist2;

    queue<ll> q;
    q.push(initialNode);

    ll maxDist = 0;
    ll diameterNode1 = initialNode;

    while(!q.empty()) {
        ll v = q.front(); q.pop();

        if(vis[v]) continue;
        vis[v] = true;

        if(dist1[v] > maxDist) {
            maxDist = dist1[v];
            diameterNode1 = v;
        }

        for(auto [u,w] : adj[v]) {
            if(vis[u]) continue;

            dist1[u] = dist1[v] + w;
            q.push(u);
        }
    }

    dist1.clear();

    q.push(diameterNode1);
    map<ll,bool> visited;

    ll diameterDistance = 0;
    ll diameterNode2 = diameterNode1;

    while(!q.empty()) {
        ll v = q.front(); q.pop();

        if(visited[v]) continue;
        visited[v] = true;

        if(dist1[v] > diameterDistance) {
            diameterDistance = dist1[v];
            diameterNode2 = v;
        }

        for(auto [u,w] : adj[v]) {
            if(visited[u]) continue;

            dist1[u] = dist1[v] + w;
            q.push(u);
        }
    }

    q.push(diameterNode2);
    visited.clear();

    ll radius = diameterDistance, radiusNode = diameterNode2;

    while(!q.empty()) {
        ll v = q.front(); q.pop();

        if(visited[v]) continue;
        visited[v] = true;

        for(auto [u,w] : adj[v]) {
            if(visited[u]) continue;

            dist2[u] = dist2[v] + w;

            if(max(dist1[u], dist2[u]) < radius) {
                radius = max(dist1[u], dist2[u]);
                radiusNode = u;
            }

            q.push(u);
        }
    }

    return {radiusNode, radius};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    vector<vector<pair<ll,ll>>> adj(N+1);

    for(int i = 0; i < M; i++){
        adj[A[i]].emplace_back(B[i],T[i]);
        adj[B[i]].emplace_back(A[i],T[i]);
    }

    ll totalComponents = N - M;

    vector<ll> radiusNodes(totalComponents);

    vector<bool> vis(N);

    ll curComponent = 0;
    ll centralNode = 0;
    ll maxComponentRadius = 0;

    for(int i = 0; i < N; i++){
        if(vis[i]) continue;

        pair<ll,ll> radius = getRadiusNode(i,adj,vis);
        radiusNodes[curComponent] = radius.first;

        if(radius.second > maxComponentRadius) {
            maxComponentRadius = radius.second;
            centralNode = radius.first;
        }

        ++curComponent;
    }

    for (int i = 0; i < totalComponents; ++i) {
        if(centralNode == radiusNodes[i]) continue;

        adj[centralNode].emplace_back(radiusNodes[i], L);
        adj[radiusNodes[i]].emplace_back(centralNode, L);
    }

    queue<ll> q;
    vector<ll> dist(N);
    fill(vis.begin(), vis.end(), false);

    q.push(0);

    ll root = 0;
    ll maxDist = 0;

    while(!q.empty()) {
        ll v = q.front(); q.pop();

        if(vis[v]) continue;
        vis[v] = true;

        if(dist[v] > maxDist) {
            maxDist = dist[v];
            root = v;
        }

        for(auto [u,w] : adj[v]) {
            if(vis[u]) continue;

            dist[u] = dist[v] + w;
            q.push(u);
        }
    }

    fill(vis.begin(), vis.end(), false);
    fill(dist.begin(), dist.end(), 0);

    q.push(root);

    ll diameterDistance = 0;

    while(!q.empty()) {
        ll v = q.front(); q.pop();

        if(vis[v]) continue;
        vis[v] = true;

        if(dist[v] > diameterDistance) {
            diameterDistance = dist[v];
        }

        for(auto [u,w] : adj[v]) {
            if(vis[u]) continue;

            dist[u] = dist[v] + w;
            q.push(u);
        }
    }


    return diameterDistance;
}

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