Submission #1178180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178180		countless	Dreaming (IOI13_dreaming)	C++20	100 / 100	67 ms	17736 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 1e9;

vector<bool> vis;
vector<vector<pair<int, int>>> adj;

vector<int> fir, sec, ans, dia;

int mx = -1;

void dfsIn(int node, int parent = -1) {
    for (auto &[child, weight] : adj[node]) {
        if (child == parent) continue;
        dfsIn(child, node);

        if (fir[child] + weight > fir[node]) {
            sec[node] = fir[node];
            fir[node] = fir[child] + weight;
        }

        else if (fir[child] + weight > sec[node]) {
            sec[node] = fir[child] + weight;
        }
    }

    mx = max(mx, fir[node] + sec[node]);
}

int dfsOut(int node, int dist = 0) {
    vis[node] = true;

    int best;
    best = ans[node] = max(dist, fir[node]);
    for (auto &[child, weight] : adj[node]) {
        if (vis[child]) continue;

        if (fir[child] + weight == fir[node]) {
            best = min(best, dfsOut(child, max(dist, sec[node]) + weight));
        }

        else {
            best = min(best, dfsOut(child, ans[node] + weight));
        }
    }

    return best;
}

int handleConnectedComponent(int node) {
    dfsIn(node);
    return dfsOut(node);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vis.assign(N, false);
    adj.resize(N);

    fir.assign(N, 0);
    sec.assign(N, 0);
    ans.resize(N);
    dia.resize(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]});
    }

    vector<int> candidates;
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            candidates.push_back(handleConnectedComponent(i));
        }
    }

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

    if (candidates.size() == 1) {
        return mx;
    }

    else if (candidates.size() == 2) {
        return max(
            candidates[0] + candidates[1] + L,
            mx
        );
    }

    else {
        return max({
            candidates[0] + candidates[1] + L,
            candidates[1] + candidates[2] + L + L,
            mx
        });
    }
}

// void solution() {
//     int N, M, L; cin >> N >> M >> L;
//     int A[M], B[M], T[M];
//     for (int i = 0; i < M; i++) {
//         cin >> A[i] >> B[i] >> T[i];
//     }

//     cout << travelTime(N, M, L, A, B, T) << endl;
// }

// signed main() {
//     solution();
// }

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