Submission #1263437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263437		tkhoi13	Dreaming (IOI13_dreaming)	C++20	47 / 100	42 ms	14404 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define REP(i, n) for (int i = 0, _b = (n); i < _b; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define pb push_back
#define szx(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

#define pii pair<int, int>
#define ll long long

vector<pii> adj[100000];
vector<ll> dis(100000, -1);

ll ans = 0;
ll mx = 0, d = 0;
int par[100000];

void dfs(int u, int p = -1) {
    if (mx < dis[u]) mx = dis[u], d = u;
    par[u] = p;

    for (auto& [v, w] : adj[u]) {
        if (v != p) {
            dis[v] = dis[u] + w;
            dfs(v, u);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    REP(i, M) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }

    vector<ll> half;

    // cout << dis[0] <<
    REP(i, N) if (dis[i] == -1) {
        mx = -1;
        d = 0;
        dis[i] = 0;
        dfs(i);
        int d1 = d;

        mx = -1, d = 0;
        dis[d1] = 0;
        dfs(d1);
        int d2 = d;

        ans = max(ans, mx);
        ll ans1 = LLONG_MAX;

        for (int u = d2; u != -1; u = par[u]) ans1 = min(max(dis[u], mx - dis[u]), ans1);
        // for (int u = d2; u != -1; u = par[u]) { cout << u << ' '; };
        // cout << endl;
        half.pb(ans1);
        // cout << ans1 << ' ';
    }

    sort(all(half), greater<ll>());

    if (szx(half) >= 2) { ans = max(ans, half[0] + L + half[1]); }

    for (int i = 2; i < szx(half); i++) { ans = max(ans, half[0] + i * L + half[i]); }

    return ans;
}

// int main() {
//     int N = 12;
//     int M = 8;
//     int L = 2;
//     int A[]{0, 8, 2, 5, 5, 1, 1, 10};
//     int B[]{8, 2, 7, 11, 1, 3, 9, 6};
//     int T[]{4, 2, 4, 3, 7, 1, 5, 3};

//     int x = travelTime(N, M, L, A, B, T);
//     // REP(i, N) { cout << dis[i] << ' '; }

//     cout << x;
// }

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