Submission #1178162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178162		countless	Dreaming (IOI13_dreaming)	C++20	0 / 100	28 ms	12068 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;

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;
        }
    }
}

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 dfsCheck(int node) {
//     cerr << fir[node] << " " << sec[node] << endl;
//     int best = max(fir[node], sec[node]);
//     vis[node] = true;

//     for (auto &[child, weight] : adj[node]) {
//         if (vis[child]) continue;
//         best = min(best, dfsCheck(child));
//     }

//     return best;
// }

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

    // return dfsCheck(node);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    // A and B are edge lists - A to B bidiectinoaly
    vis.assign(N, false);
    adj.resize(N);

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

    else {
        return candidates[0] + candidates[1] + L;
    }
}

// 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: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23