Submission #679889

#	Time	Username	Problem	Language	Result	Execution time	Memory
679889		bashkort	Dreaming (IOI13_dreaming)	C++17	100 / 100	79 ms	24492 KiB

dreaming

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

using namespace std;

constexpr int N = 100000;

vector<pair<int, int>> adj[N];

int dp[N], now = numeric_limits<int>::max(), ans = 0;

bool used[N];

void dfs1(int v, int par) {
    used[v] = true;
    for (auto [to, w] : adj[v]) {
        if (to != par) {
            dfs1(to, v);
            ans = max(ans, dp[v] + dp[to] + w);
            dp[v] = max(dp[v], dp[to] + w);
        }
    }
}

void dfs2(int v, int par, int up) {
    now = min({now, max(up, dp[v])});
    vector<int> pref(adj[v].size() + 1);
    for (int i = 0; i < adj[v].size(); ++i) {
        pref[i + 1] = pref[i];

        auto [to, w] = adj[v][i];

        if (to == par) {
            continue;
        }

        pref[i + 1] = max(pref[i + 1], dp[to] + w);
    }

    for (int i = int(adj[v].size()) - 1; i >= 0; --i) {
        auto [to, w] = adj[v][i];

        if (to == par) {
            continue;
        }

        dfs2(to, v, max(pref[i], up) + w);

        up = max(up, dp[to] + w);
    }
}

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]);
    }

    vector<int> arr;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            now = numeric_limits<int>::max();

            dfs1(i, -1);
            dfs2(i, -1, 0);

            arr.push_back(now);
        }
    }

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

    if (arr.size() > 1) {
        ans = max(ans, arr[0] + arr[1] + L);
    }
    if (arr.size() > 2) {
        ans = max(ans, arr[1] + arr[2] + 2 * L);
    }

    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < adj[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~

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