Submission #1240046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240046		shadowcoder	Dreaming (IOI13_dreaming)	C++20	100 / 100	43 ms	16840 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, max2));
        else dfsUp(to, node, w + max(above, max1));
    }
}

long long dp2[maxn];

void dfsSlow(int root, int node, int par, long long curr)
{
    dp2[root] = max(dp2[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);

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