oj.uz

Submission #433337

# Submission time Handle Problem Language Result Execution time Memory
433337 2021-06-19T15:24:32 Z illyakr Dreaming (IOI13_dreaming) C++14
0 / 100
 69 ms 12764 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

struct Info {
    int a, ta, coa;
    int b, tb, cob;
};
int SAVE = 0;
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;
        }
    }
    SAVE = max(SAVE, sv[v].a + sv[v].b + sv[v].coa + sv[v].cob);
//    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 max(f, SAVE);
    if (M == N - 2)return max(f + s + L, SAVE);
    return max({f + L + s, t + L + L + s, SAVE});
}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 12764 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 69 ms 12764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

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 69 ms 12764 KB Output isn't correct
2 Halted 0 ms 0 KB -