oj.uz

Submission #394428

# Submission time Handle Problem Language Result Execution time Memory
394428 2021-04-26T15:38:22 Z phathnv Dreaming (IOI13_dreaming) C++11
32 / 100
 87 ms 21956 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 = 0; 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21956 KB Output is correct
2 Correct 75 ms 20888 KB Output is correct
3 Correct 53 ms 20324 KB Output is correct
4 Correct 14 ms 5444 KB Output is correct
5 Correct 9 ms 3916 KB Output is correct
6 Correct 19 ms 6904 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 37 ms 10288 KB Output is correct
9 Correct 49 ms 16304 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 75 ms 15848 KB Output is correct
12 Correct 87 ms 18884 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Incorrect 2 ms 2636 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21956 KB Output is correct
2 Correct 75 ms 20888 KB Output is correct
3 Correct 53 ms 20324 KB Output is correct
4 Correct 14 ms 5444 KB Output is correct
5 Correct 9 ms 3916 KB Output is correct
6 Correct 19 ms 6904 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 37 ms 10288 KB Output is correct
9 Correct 49 ms 16304 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 75 ms 15848 KB Output is correct
12 Correct 87 ms 18884 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6600 KB Output is correct
2 Correct 28 ms 6604 KB Output is correct
3 Correct 30 ms 6576 KB Output is correct
4 Correct 29 ms 6524 KB Output is correct
5 Correct 29 ms 6500 KB Output is correct
6 Correct 31 ms 6920 KB Output is correct
7 Correct 32 ms 6680 KB Output is correct
8 Correct 28 ms 6440 KB Output is correct
9 Correct 28 ms 6456 KB Output is correct
10 Correct 29 ms 6664 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 9 ms 4424 KB Output is correct
13 Correct 9 ms 4552 KB Output is correct
14 Correct 9 ms 4424 KB Output is correct
15 Correct 9 ms 4424 KB Output is correct
16 Correct 9 ms 4424 KB Output is correct
17 Correct 8 ms 4168 KB Output is correct
18 Correct 12 ms 4552 KB Output is correct
19 Correct 9 ms 4424 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2636 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 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Incorrect 2 ms 2636 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21956 KB Output is correct
2 Correct 75 ms 20888 KB Output is correct
3 Correct 53 ms 20324 KB Output is correct
4 Correct 14 ms 5444 KB Output is correct
5 Correct 9 ms 3916 KB Output is correct
6 Correct 19 ms 6904 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 37 ms 10288 KB Output is correct
9 Correct 49 ms 16304 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 75 ms 15848 KB Output is correct
12 Correct 87 ms 18884 KB Output is correct
13 Correct 3 ms 2764 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Halted 0 ms 0 KB -