Submission #1301955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301955		regulardude6	Dreaming (IOI13_dreaming)	C++20	100 / 100	49 ms	10384 KiB

dreaming

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

using ll = long long;

struct Edge{
    int to;
    int w;
};

static vector<vector<Edge>> g;
static vector<ll> dist_arr;
static vector<int> dist_used;

static pair<int,ll> bfsFarthest(int src, const vector<char>& inComp) {
    queue<int> q;
    dist_arr[src] = 0;
    dist_used.clear();
    dist_used.push_back(src);
    q.push(src);
    int bestNode = src;
    ll bestDist = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        ll d = dist_arr[v];
        if (d > bestDist) {
            bestDist = d;
            bestNode = v;
        }
        for (auto &e : g[v]) {
            int u = e.to;
            if (!inComp[u]) continue;
            if (dist_arr[u] != -1) continue;
            dist_arr[u] = d + e.w;
            dist_used.push_back(u);
            q.push(u);
        }
    }
    return {bestNode, bestDist};
}

static void resetDist() {
    for (int v : dist_used) {
        dist_arr[v] = -1;
    }
    dist_used.clear();
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.assign(N, {});
    for (int i = 0; i < M; i++) {
        int a = A[i], b = B[i], w = T[i];
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    dist_arr.assign(N, -1);
    dist_used.reserve(N);

    vector<char> visited(N, 0), inComp(N, 0);
    vector<ll> radii;
    ll maxDiam = 0;

    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;
        vector<int> nodes;
        stack<int> st;
        st.push(i);
        visited[i] = 1;
        while (!st.empty()) {
            int v = st.top(); st.pop();
            nodes.push_back(v);
            inComp[v] = 1;
            for (auto &e : g[v]) {
                int u = e.to;
                if (!visited[u]) {
                    visited[u] = 1;
                    st.push(u);
                }
            }
        }
        int anyNode = nodes[0];
        auto a = bfsFarthest(anyNode, inComp);
        int nodeA = a.first;
        resetDist();
        auto b = bfsFarthest(nodeA, inComp);
        int nodeB = b.first;
        vector<ll> da;
        da.reserve(nodes.size());
        for (int v : nodes) {
            da.push_back(dist_arr[v]);
        }
        resetDist();
        auto c = bfsFarthest(nodeB, inComp);
        ll diam = c.second;
        ll radius = LLONG_MAX;
        size_t idx = 0;
        for (int v : nodes) {
            ll db = dist_arr[v];
            ll dmax = max(da[idx], db);
            if (dmax < radius) radius = dmax;
            idx++;
        }
        resetDist();
        for (int v : nodes) {
            inComp[v] = 0;
        }
        radii.push_back(radius);
        if (diam > maxDiam) maxDiam = diam;
    }
    sort(radii.begin(), radii.end(), greater<ll>());
    ll ans = maxDiam;
    if ((int)radii.size() >= 2) {
        ans = max(ans, radii[0] + (ll)L + radii[1]);
    }
    if ((int)radii.size() >= 3) {
        ans = max(ans, radii[1] + 2LL * (ll)L + radii[2]);
    }
    return (int)ans;
}

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