oj.uz

Submission #1081304

# Submission time Handle Problem Language Result Execution time Memory
1081304 2024-08-29T21:45:20 Z asdasdqwer Dreaming (IOI13_dreaming) C++14
0 / 100
 31 ms 14672 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;

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

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<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>());

    // for (int &x:dia) {
    //   cout << x << " ";
    // }
    // cout<<"\n";
    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: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);
      |          ^
dreaming.cpp:38:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   38 |     auto [d3, n3] = dfs(n2, -1, dis3);
      |          ^~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6364 KB Output is correct
2 Incorrect 16 ms 6868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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