oj.uz

Submission #830945

# Submission time Handle Problem Language Result Execution time Memory
830945 2023-08-19T13:29:14 Z Kerim Dreaming (IOI13_dreaming) C++17
0 / 100
 41 ms 13012 KB 
#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+5;
vector<pii> adj[N];
vector<int> members;
bool vis[N];

void dfs0(int nd, int pr){
    vis[nd] = 1;
    members.push_back(nd);
    for (auto [to, w]: adj[nd])
        if (to != pr)
            dfs0(to, nd);
}
int max_weight, endpoint, dp[N];
void dfs(int nd, int pr, int weight){
    if (weight > max_weight){
        max_weight = weight;
        endpoint = nd;
    }
    dp[nd] = max(dp[nd], weight);
    for (auto [to, w]: adj[nd])
        if (to != pr)
            dfs(to, nd, weight+w);
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < m; i++){
        int u = A[i], v = B[i], w = T[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<int> roots;
    for (int i = 0; i < n; i++)
        if (!vis[i]){
            dfs0(i, -1);
            roots.push_back(i);
        }
    assert(roots.size() == 2);
    vector<int> d;
    int sum = L;
    for (auto root: roots){
        members.clear();
        dfs0(root, -1);

        max_weight = 0;
        dfs(root, -1, 0);
        int a = endpoint; 
        max_weight = 0;
        dfs(endpoint, -1, 0);
        int b = endpoint;
        d.push_back(max_weight);
        dfs(a, -1, 0);
        dfs(b, -1, 0);

        int value = 0;
        for (auto member: members)
            if (value > dp[member])
                value = dp[member];
        sum += value;
    }
    return max(sum, max(d[0], d[1]));
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13012 KB Output is correct
2 Correct 41 ms 12980 KB Output is correct
3 Correct 25 ms 9548 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5052 KB Output is correct
7 Incorrect 1 ms 2656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13012 KB Output is correct
2 Correct 41 ms 12980 KB Output is correct
3 Correct 25 ms 9548 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5052 KB Output is correct
7 Incorrect 1 ms 2656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 12188 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13012 KB Output is correct
2 Correct 41 ms 12980 KB Output is correct
3 Correct 25 ms 9548 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 6 ms 3540 KB Output is correct
6 Correct 11 ms 5052 KB Output is correct
7 Incorrect 1 ms 2656 KB Output isn't correct
8 Halted 0 ms 0 KB -