oj.uz

Submission #1081302

# Submission time Handle Problem Language Result Execution time Memory
1081302 2024-08-29T21:32:31 Z asdasdqwer Dreaming (IOI13_dreaming) C++14
0 / 100
 41 ms 24320 KB 
#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;
}

int diameter(int node) {
    dis1[node]=0;
    dfs(node, -1, dis1);

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

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

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

    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<int> dia;
    for (int i=0;i<N;i++) {
        if (vis[i]) continue;
        dia.push_back(diameter(i));
    }
    sort(dia.begin(), dia.end(), greater<int>());
    return dia[0] + dia[1] + L;
}

Compilation message

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 'int diameter(int)':
dreaming.cpp:37:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     auto [n1, d1] = dfs(node, -1, dis1);
      |          ^
dreaming.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     auto [n2, d2] = dfs(n1, -1, dis2);
      |          ^
dreaming.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [n3, d3] = dfs(n2, -1, dis2);
      |          ^
dreaming.cpp:39:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   39 |     auto [n3, d3] = dfs(n2, -1, dis2);
      |          ^~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 24320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 24320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 6876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 24320 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -