Submission #1316620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316620		the_commando_x	꿈 (IOI13_dreaming)	C++17	0 / 100	29 ms	11628 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

const int MAXN = 1e5;

vector<vector<pair<int, int>>> adj(MAXN);

vector<bool> vis(MAXN, false);
vector<int> dist(MAXN, 0);

int curmn = -1, curmx = -1; // {radius, diameter}

void dfs(int u, int par)
{
    vis[u] = true;

    dist[u] = 0;
    for (auto [v, d] : adj[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        dist[u] = max(dist[u], dist[v] + d);
    }
}

void reroot(int u, int par)
{
    int mx1 = 0, mx2 = 0;

    for (auto &[v, d] : adj[u])
    {
        if (v == par)
            continue;

        int val = dist[v] + d;
        if (val > mx1)
        {
            mx2 = mx1;
            mx1 = val;
        }
        else if (val > mx2)
            mx2 = val;
    }

    int old = dist[u];
    dist[u] = mx1;

    curmn = min(curmn, dist[u]);
    curmx = max(curmx, mx1 + mx2);

    for (auto &[v, d] : adj[u])
    {
        if (v == par)
            continue;

        int saved = dist[u];

        if (dist[v] + d == mx1)
            dist[u] = mx2;

        reroot(v, u);

        dist[u] = saved;
    }

    dist[u] = old;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (int i = 0; i < M; ++i)
    {
        int u = A[i], v = B[i], d = T[i];
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

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

        dfs(i, -1);

        curmn = INF;
        curmx = 0;
        reroot(i, -1);

        a.push_back(curmn);
        globalDia = max(globalDia, curmx);
    }

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

    int ans = 0;
    if (a.size() >= 2)
        ans = max(ans, a[0] + L + a[1]);
    if (a.size() >= 3)
        ans = max(ans, a[1] + 2 * L + a[2]);
    return max(ans, globalDia);
}

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