제출 #1240025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240025		shadowcoder	꿈 (IOI13_dreaming)	C++20	40 / 100	1096 ms	12524 KiB

dreaming

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

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 60);

vector<pair<int, int>> g[maxn];
bool visited[maxn];

long long down[maxn];
long long dp[maxn];
vector<int> nodes;

void dfsDown(int node, int par)
{
    nodes.push_back(node);
    visited[node] = true;
    down[node] = 0;

    for (auto [to, w] : g[node])
    {
        if (to != par)
        {
            dfsDown(to, node);
            down[node] = max(down[node], down[to] + w);
        }
    }
}

void dfsUp(int node, int par, long long above)
{
    dp[node] = max(down[node], above);

    long long max1 = -1, max2 = -1;
    int node1 = -1, node2 = -1;

    for (auto [to, w] : g[node])
    {
        if (to == par) continue;
        if (max1 < w + down[to])
        {
            max2 = max1;
            node2 = node1;
            max1 = w + down[to];
            node1 = to;
        }
        else if (max2 < w + down[to])
        {
            max2 = w + down[to];
            node2 = to;
        }
    }

    for (auto [to, w] : g[node])
    {
        if (to == par) continue;
        if (to == node1) dfsUp(to, node, w + max(above, above + max2));
        else dfsUp(to, node, w + max(above, above + max1));
    }
}

void dfsSlow(int root, int node, int par, long long curr)
{
    dp[root] = max(dp[root], curr);

    for (auto [to, w] : g[node])
    {
        if (to != par)
        {
            dfsSlow(root, to, node, curr + w);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (int i = 0; i < M; ++i)
    {
        int x = A[i], y = B[i], w = T[i];
        ++x;
        ++y;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    vector<long long> dists;
    long long ans = 0;

    for (int i = 1; i <= N; ++i)
    {
        if (visited[i] == false)
        {
            nodes.clear();
            dfsDown(i, -1);
            //dfsUp(i, -1, 0);
            
            for (auto node : nodes)
            {
                dfsSlow(node, node, -1, 0);
            }

            long long minDist = inf, maxDist = 0;
            for (auto node : nodes)
            {
                //cout << "here " << node << " :: " << down[node] << " and " << dp[node] << endl;
                maxDist = max(maxDist, dp[node]);
                minDist = min(minDist, dp[node]);
            }

            dists.push_back(minDist);
            ans = max(ans, maxDist);
            //cout << "-------------" << endl;
        }
    }

    //cout << "here " << ans << endl;

    sort(dists.begin(), dists.end());
    if (dists.size() == 1) return ans;
    if (dists.size() == 2)
    {
        ans = max(ans, dists[0] + dists[1] + L);
    }
    else
    {
        long long max1 = dists[dists.size() - 1];
        long long max2 = dists[dists.size() - 2];
        long long max3 = dists[dists.size() - 3];
        ans = max(ans, max1 + L + max2);
        ans = max(ans, max2 + max3 + 2 * L);
    }

    return ans;
}

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