oj.uz

Submission #433333

# Submission time Handle Problem Language Result Execution time Memory
433333 2021-06-19T15:21:32 Z illyakr Dreaming (IOI13_dreaming) C++14
18 / 100
 73 ms 12736 KB 
#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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7296 KB Output is correct
2 Correct 24 ms 7244 KB Output is correct
3 Correct 26 ms 7244 KB Output is correct
4 Correct 34 ms 7248 KB Output is correct
5 Correct 27 ms 7244 KB Output is correct
6 Correct 32 ms 7484 KB Output is correct
7 Correct 29 ms 7500 KB Output is correct
8 Correct 26 ms 7116 KB Output is correct
9 Correct 21 ms 7116 KB Output is correct
10 Correct 24 ms 7416 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 5 ms 5144 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 5 ms 5012 KB Output is correct
18 Correct 5 ms 5136 KB Output is correct
19 Correct 6 ms 5068 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 2 ms 2764 KB Output is correct
23 Correct 5 ms 5068 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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