Submission #587108

#	Time	Username	Problem	Language	Result	Execution time	Memory
587108		usuyus	Dreaming (IOI13_dreaming)	C++14	100 / 100	92 ms	21276 KiB

dreaming

#include "dreaming.h"

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<array<int, 2>>> fore(N);

    for (int i=0; i<M; i++) {
        fore[A[i]].push_back({B[i], T[i]});
        fore[B[i]].push_back({A[i], T[i]});
    }

    int ans = 0;
    vector<bool> vis(N);
    vector<int> len(N);

    function<int(int, int)> len_dfs = [&] (int nd, int par) {
        vis[nd] = true;
        int mx1 = 0, mx2 = 0;

        for (auto [cld, t] : fore[nd]) {
            if (cld == par) continue;
            int res = len_dfs(cld, nd) + t;

            if (res > mx1) swap(mx1, res);
            if (res > mx2) swap(mx2, res);
        }

        ans = max(ans, mx1 + mx2);
        return len[nd] = mx1;
    };

    function<int(int, int, int)> best_dfs = [&] (int nd, int par, int top) {
        int mx1 = 0, mx2 = 0;
        int mx_cld = -1;
        int ret = max(top, len[nd]);

        // cout << nd << " -> " << ret << endl;

        for (auto [cld, t] : fore[nd]) {
            if (cld == par) continue;
            int res = len[cld] + t;
            
            if (res > mx1) swap(mx1, res), mx_cld = cld;
            if (res > mx2) swap(mx2, res);
        }

        for (auto [cld, t] : fore[nd]) {
            if (cld == par) continue;

            if (cld == mx_cld) {
                ret = min(ret, best_dfs(cld, nd, max(top, mx2) + t));
            } else {
                ret = min(ret, best_dfs(cld, nd, max(top, mx1) + t));
            }
        }

        return ret;
    };

    vector<int> tails;

    for (int nd=0; nd<N; nd++) {
        if (vis[nd]) continue;

        len_dfs(nd, -1);
        tails.push_back(best_dfs(nd, -1, 0));
    }

    sort(tails.rbegin(), tails.rend());
    if (tails.size() >= 2) ans = max(ans, tails[0] + L + tails[1]);
    if (tails.size() >= 3) ans = max(ans, tails[1] + 2*L + tails[2]);

    return ans;
}

Compilation message (stderr)

dreaming.cpp: In lambda function:
dreaming.cpp:22:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         for (auto [cld, t] : fore[nd]) {
      |                   ^
dreaming.cpp: In lambda function:
dreaming.cpp:41:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for (auto [cld, t] : fore[nd]) {
      |                   ^
dreaming.cpp:49:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for (auto [cld, t] : fore[nd]) {
      |                   ^

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