oj.uz

Submission #519919

# Submission time Handle Problem Language Result Execution time Memory
519919 2022-01-27T19:00:33 Z PiejanVDC Dreaming (IOI13_dreaming) C++17
18 / 100
 90 ms 35960 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int mxN = (int)1e5+5;

vector<pair<int,int>>adj[mxN];
vector<bool>vis(mxN);

pair<int,int> find_leaf(int u, int e = -1) {
    vis[u] = 1;
    pair<int,int>ret = {u, 0};
    for(auto v : adj[u]) if(v.first != e) {
        auto nxt = find_leaf(v.first,u);
        if(nxt.second + v.second > ret.second) {
            ret.first = nxt.first, ret.second = nxt.second + v.second;
        }
    }
    return ret;
}

int prevv[mxN];

int calc_diameter(int u, int e = -1) {
    int ret = 0;
    for(auto v : adj[u]) if(v.first != e) {
        int d_ = calc_diameter(v.first,u) + v.second;
        if(d_ > ret) {
            ret = d_;
            prevv[u] = v.first;
        }
    }
    return ret;
}

set<int>fn;
vector<int>node(mxN);
int val;

map<pair<int,int>,int>lenof;
bool ok;

void calc_set(int u) {
    fn.insert(val);
    node[val] = u;
    if((!ok && (int)adj[u].size() == 1) || (int)adj[u].size() == 0)
        return;
    ok = 0;
    val += lenof[{min(u,prevv[u]), max(u,prevv[u])}];
    calc_set(prevv[u]);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0 ; i < M ; i++) {
        adj[A[i]].emplace_back(B[i],T[i]);
        adj[B[i]].emplace_back(A[i],T[i]);
        lenof[{min(A[i],B[i]), max(A[i],B[i])}] = T[i];
    }
    int global_max = -1, global_mid;
    vector<int>r_;
    for(int root = 0 ; root < N ; root++) if(!vis[root]) {
        int leaf = find_leaf(root).first;
        int len = calc_diameter(leaf);
        ok = 1;
        calc_set(leaf);
        int mx = -1;
        int r;
        auto it = lower_bound(fn.begin(),fn.end(),len/2);
        assert(it != fn.end());
        mx = max(*it, len - *it);
        r = node[*it];
        if(it != fn.begin()) {
            it--;
            if(max(*it, len - *it) < mx) {
                mx = max(*it, len - *it);
                r = node[*it];
            }
        }
        r_.push_back(r);
        if(mx > global_max) {
            global_max = mx;
            global_mid = r;
        }
        fn.clear();
        val = 0;
    }
    for(auto rr : r_) if(rr != global_mid) {
        adj[rr].emplace_back(global_mid, L);
        adj[global_mid].emplace_back(rr, L);
    }
    int leaf = find_leaf(0).first;
    return calc_diameter(leaf);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 35960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 1 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 2 ms 3020 KB Output is correct
9 Correct 1 ms 3020 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 2 ms 2992 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Runtime error 4 ms 5964 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 35960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9280 KB Output is correct
2 Correct 42 ms 9412 KB Output is correct
3 Correct 38 ms 9308 KB Output is correct
4 Correct 46 ms 9412 KB Output is correct
5 Correct 42 ms 9360 KB Output is correct
6 Correct 47 ms 10232 KB Output is correct
7 Correct 56 ms 9844 KB Output is correct
8 Correct 37 ms 9276 KB Output is correct
9 Correct 39 ms 9148 KB Output is correct
10 Correct 61 ms 9552 KB Output is correct
11 Correct 2 ms 3020 KB Output is correct
12 Correct 13 ms 7744 KB Output is correct
13 Correct 13 ms 7736 KB Output is correct
14 Correct 13 ms 7744 KB Output is correct
15 Correct 13 ms 7744 KB Output is correct
16 Correct 13 ms 7688 KB Output is correct
17 Correct 12 ms 7528 KB Output is correct
18 Correct 13 ms 7704 KB Output is correct
19 Correct 13 ms 7744 KB Output is correct
20 Correct 2 ms 3020 KB Output is correct
21 Correct 2 ms 3020 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Correct 12 ms 7744 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 1 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 2 ms 3020 KB Output is correct
9 Correct 1 ms 3020 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 2 ms 2992 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Runtime error 4 ms 5964 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 35960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -