제출 #1318164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318164		kutomei3	꿈 (IOI13_dreaming)	C++20	0 / 100	1093 ms	12404 KiB

dreaming

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

vector<int> sr[100001];
void ff(vector<pair<int, int>> ap[], int cur, int par, int g)
{
    sr[g].push_back(cur);
    for (auto& [p, w] : ap[cur]) {
        if (p == par) continue;
        ff(ap, p, cur, g);
    }
}

vector<int> mn(100005, -1);
vector<int> dij(vector<pair<int, int>> ap[], int n, int s, int g) {
    for (auto& p : sr[g]) mn[p] = 2e9; 
    mn[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({mn[s], s});

    while (pq.size()) {
        auto [w, u] = pq.top();
        pq.pop();

        if (mn[u] < w) continue; 

        for (auto& [v, d] : ap[u]) {
            if (mn[v] > w + d) {
                mn[v] = w + d;
                pq.push({mn[v], v});
            }
        }
    }

    //for (auto& p : sr[g]) cout << mn[p] << ' ';
    //cout << '\n';

    return mn;
}

int findc(vector<pair<int, int>> ap[], int n, int s, int g)
{
    vector<int> sm = dij(ap, n, s, g);

    int l = s;
    for (auto& p : sr[g]) {
        //cout << mn[p] << ' ';
        if (mn[p] > mn[l]) l = p;
    }

    //cout << mn[l] << ' ';
    
    vector<int> lm = dij(ap, n, l, g);

    int r = l;
    for (auto& p : sr[g]) {
        if (mn[p] > mn[r]) r = p;
    }

    vector<int> rm = dij(ap, n, r, g);

    int md = 2e9;
    for (auto& p : sr[g]) {
        md = min(md, max(lm[p], rm[p]));
    }

    return md; 
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    vector<pair<int, int>> ap[n + 1];
    for (int i = 0; i < m; i++) {
        ap[A[i]].push_back({B[i], T[i]});
        ap[B[i]].push_back({A[i], T[i]});
    }
    int g = 0;
    int f1, f2, f3;
    vector<int> arr;
    for (int i = 0; i < n; i++) {
        if (mn[i] == -1) {
            ff(ap, i, -1, ++g);
            int val = findc(ap, n, i, g);
            arr.push_back(val);
        }
    }

    sort(arr.rbegin(), arr.rend());

    //for (auto& p : arr) cout << p << ' ';
    //cout << '\n';

    int ans;
    if (arr.size() <= 2) ans = arr[0] + arr[1] + l;
    else ans = max(arr[0] + arr[1] + l, l * 2 + arr[1] + arr[2]);

    return ans;
}

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