제출 #335992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335992		arujbansal	꿈 (IOI13_dreaming)	C++17	100 / 100	159 ms	14188 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;

const int MAXN = 1e5 + 5, INF = 1e9 + 5;
using ll = long long;

vector<pair<int, int>> g[MAXN];
vector<pair<int, int>> bestComps;
bool vis[MAXN];
pair<int, int> leaf[2];
pair<int, int> optimalRoot;
int diameterDist[MAXN][2];

void diameter(int u, int p, int dist, int idx) {
    vis[u] = true;

    leaf[idx] = max(leaf[idx], make_pair(dist, u));
    diameterDist[u][idx] = dist;

    optimalRoot = min(optimalRoot, make_pair(max(diameterDist[u][0], diameterDist[u][1]), u));

    for (const auto &[v, wt] : g[u]) {
        if (v == p) continue;
        diameter(v, u, dist + wt, idx);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }

    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;

        leaf[0] = leaf[1] = {-INF, -INF};

        diameter(i, -1, 0, 0);
        diameter(leaf[0].second, -1, 0, 1);
        optimalRoot = {INF, i};
        diameter(leaf[1].second, -1, 0, 0);

        bestComps.emplace_back(optimalRoot.first, optimalRoot.second);
    }

    int best = (*max_element(bestComps.begin(), bestComps.end())).second;
    
    for (int i = 0; i < int(bestComps.size()); i++) {
        int v = bestComps[i].second;

        if (best == v) continue;

        g[best].emplace_back(v, L);
        g[v].emplace_back(best, L);
    }

    leaf[0] = leaf[1] = {-INF, -INF};

    diameter(0, -1, 0, 0);
    diameter(leaf[0].second, -1, 0, 1);

    return leaf[1].first;
}

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