oj.uz

Submission #155846

# Submission time Handle Problem Language Result Execution time Memory
155846 2019-10-01T04:48:41 Z TAISA_ Dreaming (IOI13_dreaming) C++14
18 / 100
 124 ms 25080 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (1 << 30) - 1;
const ll LINF = (1LL << 60) - 1LL;
vector<vector<P>> G;
vector<int> dep, dp, vis;
vector<multiset<int>> st;
void build(int i, int p, int d) {
    vis[i] = 1;
    dep[i] = d;
    dp[i] = dep[i];
    for (auto &e : G[i]) {
        if (e.first == p) {
            continue;
        }
        build(e.first, i, d + e.second);
        dp[i] = max(dp[i], dp[e.first]);
        st[i].insert(dp[e.first] - dep[i]);
    }
}
pair<int, int> calc(int i, int p) {
    int res = INF, dia = 0;
    if (st[i].size() > 0) {
        auto itr = st[i].end();
        --itr;
        res = (*itr);
    }
    if (st[i].size() > 1) {
        auto itr = st[i].end();
        --itr;
        dia += (*itr);
        --itr;
        dia += (*itr);
    }
    for (auto &e : G[i]) {
        if (e.first == p) {
            continue;
        }
        int t = dp[e.first] - dep[i];
        st[i].erase(st[i].find(t));
        if (st[i].size() > 0) {
            auto it = st[i].end();
            --it;
            st[e.first].insert((*it) + e.second);
        } else {
            st[e.first].insert(e.second);
        }
        pair<int, int> re = calc(e.first, i);
        res = min(res, re.first);
        dia = max(res, re.second);
        st[i].insert(t);
    }
    //  cout << i << " " << res << endl;
    return make_pair(res, dia);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    if (M == N - 1) {
        return 0;
    }
    G.resize(N);
    st.resize(N);
    dep.resize(N);
    dp.resize(N);
    vis.resize(N);
    for (int i = 0; i < M; i++) {
        G[A[i]].push_back(P(B[i], T[i]));
        G[B[i]].push_back(P(A[i], T[i]));
    }
    vector<ll> s;
    ll ma = 0;
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            if (G[i].size() == 0) {
                s.push_back(0);
                continue;
            }
            build(i, -1, 0);
            pair<int, int> re = calc(i, -1);
            ma = max(ma, (ll)re.second);
            s.push_back(re.first);
        }
    }
    sort(all(s));
    reverse(all(s));
    ll ans = ma;
    if (s.size() > 1) {
        ans = max(ans, s[0] + s[1] + L);
    }
    if (s.size() > 2) {
        ans = max(ans, s[1] + s[2] + 2LL * L);
    }
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 25080 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 47 ms 13808 KB Output is correct
2 Correct 49 ms 13860 KB Output is correct
3 Correct 58 ms 13728 KB Output is correct
4 Correct 47 ms 13836 KB Output is correct
5 Correct 50 ms 13808 KB Output is correct
6 Correct 66 ms 15088 KB Output is correct
7 Correct 62 ms 14428 KB Output is correct
8 Correct 58 ms 13552 KB Output is correct
9 Correct 64 ms 13424 KB Output is correct
10 Correct 60 ms 14324 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 13 ms 9712 KB Output is correct
13 Correct 15 ms 9812 KB Output is correct
14 Correct 12 ms 9712 KB Output is correct
15 Correct 13 ms 9684 KB Output is correct
16 Correct 15 ms 9712 KB Output is correct
17 Correct 12 ms 9712 KB Output is correct
18 Correct 13 ms 9840 KB Output is correct
19 Correct 12 ms 9712 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 3 ms 636 KB Output is correct
23 Correct 13 ms 9712 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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