Submission #433333

#	Time	Username	Problem	Language	Result	Execution time	Memory
433333		illyakr	Dreaming (IOI13_dreaming)	C++14	18 / 100	73 ms	12736 KiB

dreaming

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

struct Info {
    int a, ta, coa;
    int b, tb, cob;
};
Info sv[101010];
vector<pair<int, int> > g[101010];
bool used[101010];
void dfs(int v, int pred) {
    used[v] = true;
    sv[v] = {0, v, 0, 0, v, 0};
    for (auto [to, c] : g[v]) {
        if (to == pred)continue;
        dfs(to, v);
        if (sv[v].a < sv[to].a + c) {
            sv[v].b = sv[v].a;
            sv[v].tb = sv[v].ta;
            sv[v].cob = sv[v].coa;

            sv[v].a = sv[to].a + c;
            sv[v].ta = to;
            sv[v].coa = c;
        } else if (sv[v].b < sv[to].a + c) {
            sv[v].b = sv[to].a + c;
            sv[v].tb = to;
            sv[v].cob = c;
        }
    }
//    cout << v-1 << " ---   " << sv[v].a << " " << sv[v].ta-1 << "  ;;  " << sv[v].b << " " << sv[v].tb-1 << endl;
}

int MX = 1010101010;
void psh(int v, int val, int pred) {
    MX = min(MX, max({val, sv[v].a, sv[v].b}));
    for (auto [to, c] : g[v]) {
        if (to == pred)continue;
        if (to == sv[v].ta)psh(to, max(val, sv[v].b) + c, v);
        else psh(to, max(val, sv[v].a) + c, v);
    }
}
int f, s, t;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 1; i <= M; i++) {
        g[A[i - 1] + 1].push_back({B[i - 1] + 1, T[i - 1]});
        g[B[i - 1] + 1].push_back({A[i - 1] + 1, T[i - 1]});
    }
    for (int i = 1; i <= N; i++) {
        if (used[i])continue;
        dfs(i, i);
        MX = 1010101010;
        psh(i, 0, i);
        if (f < MX) {
            t = s;
            s = f;
            f = MX;
        } else if (s < MX) {
            t = s;
            s = MX;
        } else if (t < MX) {
            t = MX;
        }
//        cout << endl;
    }
    if (M == N - 1)return f;
    if (M == N - 2)return f + s + L;
    return max(f + L + s, t + L + L + s);
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for (auto [to, c] : g[v]) {
      |               ^
dreaming.cpp: In function 'void psh(int, int, int)':
dreaming.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [to, c] : g[v]) {
      |               ^

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