Submission #225849

#	Time	Username	Problem	Language	Result	Execution time	Memory
225849		DS007	Dreaming (IOI13_dreaming)	C++14	100 / 100	186 ms	27768 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MN = 1e5 + 5;
vector<pair<int, int>> adj[MN];
bool explored[MN];
vector<int> dia, dist;
multimap<int, int> m[MN];
int dp[MN];

int dfs(int v, int p = -1, int last = 0) {
    int val = max(last, dp[v]);
    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        auto itr = m[v].rbegin();
        if (itr->second == i.first && m[v].size() == 1)
            val = min(val, dfs(i.first, v, last + i.second));
        else if (itr->second == i.first)
            val = min(val, dfs(i.first, v, max(last, (++itr)->first) + i.second));
        else
            val = min(val, dfs(i.first, v, max(last, itr->first) + i.second));
    }

    dp[v] = max(dp[v], last);
    return val;
}

void pre(int v) {
    explored[v] = true;
    for (auto i : adj[v]) {
        if (!explored[i.first])
            pre(i.first), m[v].insert({dp[i.first] + i.second, i.first});
    }
    dp[v] = m[v].empty() ? 0 : m[v].rbegin()->first;
}

pair<int, int> longest(int v, int p = -1) {
    pair<int, int> ans = {0, v};
    for (auto i : adj[v]) {
        if (i.first == p)
            continue;

        auto temp = longest(i.first, v);
        ans = max(ans, {temp.first + i.second, temp.second});
    }
    return ans;
}

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

    for (int i = 0; i < N; i++) {
        if (!explored[i]) {
            pre(i), dist.push_back(dfs(i));
            auto temp = longest(i);
            dia.push_back(longest(temp.second).first);
        }
    }

    sort(dist.begin(), dist.end(), greater<>());
    int ans = *max_element(dia.begin(), dia.end());
    if (dist.size() > 1)
        ans = max(ans, dist[0] + dist[1] + L);
    if (dist.size() > 2)
        ans = max(ans, dist[1] + dist[2] + L * 2);
    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