oj.uz

답안 #433328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433328 2021-06-19T15:11:45 Z illyakr 꿈 (IOI13_dreaming) C++14
18 / 100
 50 ms 13632 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) {
    MX = min(MX, max({val, sv[v].a, sv[v].b}));
    if (max({val, sv[v].a, sv[v].b}) <=
        max({max(val, sv[v].b) + sv[v].coa, sv[sv[v].ta].a, sv[sv[v].ta].b}))return;
    psh(sv[v].ta, max(val, sv[v].b) + sv[v].coa);
}
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);
        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]) {
      |               ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 7704 KB Output is correct
2 Correct 25 ms 7684 KB Output is correct
3 Correct 24 ms 7680 KB Output is correct
4 Correct 24 ms 7628 KB Output is correct
5 Correct 24 ms 7676 KB Output is correct
6 Correct 25 ms 8012 KB Output is correct
7 Correct 25 ms 7952 KB Output is correct
8 Correct 23 ms 7624 KB Output is correct
9 Correct 26 ms 7576 KB Output is correct
10 Correct 26 ms 7832 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 5 ms 5152 KB Output is correct
13 Correct 5 ms 5124 KB Output is correct
14 Correct 6 ms 5068 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 4 ms 5112 KB Output is correct
18 Correct 5 ms 5216 KB Output is correct
19 Correct 4 ms 5120 KB Output is correct
20 Correct 2 ms 2632 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 2 ms 2684 KB Output is correct
23 Correct 5 ms 5112 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -