oj.uz

Submission #519922

# Submission time Handle Problem Language Result Execution time Memory
519922 2022-01-27T19:02:42 Z PiejanVDC Dreaming (IOI13_dreaming) C++17
18 / 100
 115 ms 36012 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 = -1;
        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];
            }
        }
        assert(r != -1);
        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 115 ms 36012 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 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 2 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 2 ms 3020 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 2 ms 3020 KB Output is correct
12 Correct 3 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 115 ms 36012 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 41 ms 9284 KB Output is correct
2 Correct 57 ms 9400 KB Output is correct
3 Correct 54 ms 9388 KB Output is correct
4 Correct 67 ms 9432 KB Output is correct
5 Correct 77 ms 9264 KB Output is correct
6 Correct 56 ms 10272 KB Output is correct
7 Correct 42 ms 9664 KB Output is correct
8 Correct 42 ms 9276 KB Output is correct
9 Correct 49 ms 9232 KB Output is correct
10 Correct 50 ms 9592 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 7748 KB Output is correct
14 Correct 12 ms 7744 KB Output is correct
15 Correct 12 ms 7744 KB Output is correct
16 Correct 12 ms 7652 KB Output is correct
17 Correct 12 ms 7540 KB Output is correct
18 Correct 12 ms 7748 KB Output is correct
19 Correct 13 ms 7652 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 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 2 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 2 ms 3020 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 2 ms 3020 KB Output is correct
12 Correct 3 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 115 ms 36012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -