Submission #1081502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081502		asdasdqwer	Dreaming (IOI13_dreaming)	C++14	100 / 100	54 ms	17632 KiB

dreaming

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

#include "dreaming.h"

#define pii array<int,2>
#define ll long long

vector<vector<pii>> g;
vector<bool> vis;
vector<int> dis1, dis2, dis3;

pii dfs(int node, int p, vector<int> &dis) {
    vis[node]=true;
    pii ret = {dis[node], node};
    for (auto [ne, we] : g[node]) {
        if (ne == p) continue;
        dis[ne] = dis[node] + we;
        ret = max(ret, dfs(ne, node, dis));
    }
    return ret;
}

int get_diam(int node, int p, vector<int> &d1, vector<int> &d2) {
    int ret = max(d1[node], d2[node]);
    for (auto [ne, we] : g[node]) {
        if (ne == p) continue;
        ret = min(ret, get_diam(ne, node, d1, d2));
    }
    return ret;
}

pii diameter(int node) {
    dis1[node]=0;

    auto [d1, n1] = dfs(node, -1, dis1);
    auto [d2, n2] = dfs(n1, -1, dis2);
    auto [d3, n3] = dfs(n2, -1, dis3);

    return {get_diam(node, -1, dis2, dis3), d3};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    dis1.assign(N, 0);
    dis2.assign(N, 0);
    dis3.assign(N, 0);

    for (int i=0;i<M;i++) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    vis.assign(N, false);

    vector<pii> dia;
    for (int i=0;i<N;i++) {
        if (vis[i]) continue;
        dia.push_back(diameter(i));
    }
    sort(dia.begin(), dia.end(), greater<pii>());
    if (dia.size() == 1) return dia[0][1];
    if (dia.size() == 2) return max(dia[0][0] + dia[1][0] + L, max(dia[0][1], dia[1][1]));

    int mx = max(dia[0][0] + dia[1][0] + L, max(dia[0][1], dia[1][1]));
    mx = max(mx, dia[1][0] + dia[2][0] + 2*L);
    for (auto &x:dia)mx=max(mx,x[1]);
    return mx;

} 

Compilation message (stderr)

dreaming.cpp: In function 'std::array<int, 2> dfs(int, int, std::vector<int>&)':
dreaming.cpp:16:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for (auto [ne, we] : g[node]) {
      |               ^
dreaming.cpp: In function 'int get_diam(int, int, std::vector<int>&, std::vector<int>&)':
dreaming.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for (auto [ne, we] : g[node]) {
      |               ^
dreaming.cpp: In function 'std::array<int, 2> diameter(int)':
dreaming.cpp:36:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     auto [d1, n1] = dfs(node, -1, dis1);
      |          ^
dreaming.cpp:37:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     auto [d2, n2] = dfs(n1, -1, dis2);
      |          ^
dreaming.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     auto [d3, n3] = dfs(n2, -1, dis3);
      |          ^

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