Submission #1075489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075489		juicy	Dreaming (IOI13_dreaming)	C++17	100 / 100	86 ms	11376 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

using namespace std;

int travelTime(int N, int M, int L, int U[], int V[], int T[]) {
    vector<vector<array<int, 2>>> g(N);
    for (int i = 0; i < M; ++i) {
        g[U[i]].push_back({V[i], T[i]});
        g[V[i]].push_back({U[i], T[i]});
    }
    vector<int> A(N), B(N), vis(N), ver;
    int t = 0, res = 0;
    auto bfs = [&](int s, vector<int> &d) {
        vector<int>().swap(ver);
        vis[s] = ++t;
        d[s] = 0;
        queue<int> q;
        q.push(s);
        int ma = s;
        while (q.size()) {
            int u = q.front(); q.pop();
            ver.push_back(u);
            if (d[ma] < d[u]) {
                ma = u;
            }
            for (auto [v, w] : g[u]) {
                if (vis[v] != t) {
                    vis[v] = t;
                    d[v] = d[u] + w;
                    q.push(v);
                }
            }
        }
        return ma;
    };  
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < N; ++i) {
        if (!vis[i]) {
            int s = bfs(i, A);
            int t = bfs(s, A);
            bfs(t, B);
            res = max(res, B[s]);
            int mi = 1e9;
            for (int x : ver) {
                mi = min(mi, max(A[x], B[x]));
            }
            pq.push(mi);
            while (pq.size() > 3) {
                pq.pop();
            }
        }
    }
    if (pq.size() == 1) {
        return res;
    }
    if (pq.size() == 2) {
        int u = pq.top(); pq.pop();
        int v = pq.top(); pq.pop();
        return max(res, u + v + L);
    }
    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();
    int c = pq.top(); pq.pop();
    return max({res, c + b + L, a + b + 2 * L});
}

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