oj.uz

Submission #394426

# Submission time Handle Problem Language Result Execution time Memory
394426 2021-04-26T15:34:54 Z phathnv Dreaming (IOI13_dreaming) C++11
18 / 100
 85 ms 31464 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

const int N = 1e5 + 7;

vector<pair<int, int>> adj[N];
int down[N], up[N], dp[N];
bool vst[N];

void Dfs1(int u, int p){
    vst[u] = 1;
    down[u] = dp[u] = 0;
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        Dfs1(v, u);
        dp[u] = max(dp[u], down[u] + down[v] + c);
        down[u] = max(down[u], down[v] + c);
    }
}

void Dfs2(int u, int p, int &best){
    best = min(best, max(up[u], down[u]));
    multiset<int> s;
    s.insert(up[u]);
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        s.insert(down[v] + c);
    }
    for(auto e : adj[u]){
        int v = e.first;
        int c = e.second;
        if (v == p)
            continue;
        s.erase(s.find(down[v] + c));
        up[v] = *(--s.end()) + c;
        s.insert(down[v] + c);
        Dfs2(v, u, best);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i = 0; i < m; i++){
        adj[a[i]].push_back({b[i], t[i]});
        adj[b[i]].push_back({a[i], t[i]});
    }
    int res = 0;
    vector<int> vals;
    for(int i = 1; i <= n; i++){
        if (vst[i])
            continue;
        int best = 1e9;
        Dfs1(i, -1);
        Dfs2(i, -1, best);
        res = max(res, dp[i]);
        vals.push_back(best);
    }
    sort(vals.begin(), vals.end(), greater<int>());
    if (vals.size() >= 2)
        res = max(res, vals[0] + vals[1] + l);
    if (vals.size() >= 3)
        res = max(res, vals[1] + vals[2] + 2 * l);
    return res;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 27332 KB Output is correct
2 Correct 85 ms 31464 KB Output is correct
3 Correct 51 ms 16272 KB Output is correct
4 Correct 11 ms 5580 KB Output is correct
5 Correct 9 ms 4172 KB Output is correct
6 Correct 19 ms 8780 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 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 Correct 76 ms 27332 KB Output is correct
2 Correct 85 ms 31464 KB Output is correct
3 Correct 51 ms 16272 KB Output is correct
4 Correct 11 ms 5580 KB Output is correct
5 Correct 9 ms 4172 KB Output is correct
6 Correct 19 ms 8780 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6524 KB Output is correct
2 Correct 31 ms 6988 KB Output is correct
3 Correct 33 ms 6944 KB Output is correct
4 Correct 33 ms 6968 KB Output is correct
5 Correct 33 ms 6988 KB Output is correct
6 Correct 31 ms 7464 KB Output is correct
7 Correct 36 ms 7100 KB Output is correct
8 Correct 34 ms 7016 KB Output is correct
9 Correct 33 ms 6856 KB Output is correct
10 Correct 30 ms 7080 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 9 ms 4452 KB Output is correct
13 Correct 9 ms 4552 KB Output is correct
14 Correct 9 ms 4448 KB Output is correct
15 Correct 11 ms 4552 KB Output is correct
16 Correct 10 ms 4428 KB Output is correct
17 Correct 9 ms 4168 KB Output is correct
18 Correct 11 ms 4552 KB Output is correct
19 Correct 9 ms 4504 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2656 KB Output is correct
22 Correct 2 ms 2656 KB Output is correct
23 Correct 9 ms 4424 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 Correct 76 ms 27332 KB Output is correct
2 Correct 85 ms 31464 KB Output is correct
3 Correct 51 ms 16272 KB Output is correct
4 Correct 11 ms 5580 KB Output is correct
5 Correct 9 ms 4172 KB Output is correct
6 Correct 19 ms 8780 KB Output is correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Halted 0 ms 0 KB -