oj.uz

Submission #519918

# Submission time Handle Problem Language Result Execution time Memory
519918 2022-01-27T18:58:18 Z PiejanVDC Dreaming (IOI13_dreaming) C++17
18 / 100
 94 ms 37188 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);
        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 94 ms 37188 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 3 ms 3064 KB Output is correct
2 Correct 3 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 3 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3036 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 3064 KB Output is correct
11 Correct 2 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Runtime error 4 ms 6072 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 94 ms 37188 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 42 ms 9776 KB Output is correct
2 Correct 48 ms 9824 KB Output is correct
3 Correct 47 ms 9824 KB Output is correct
4 Correct 41 ms 9792 KB Output is correct
5 Correct 40 ms 9744 KB Output is correct
6 Correct 44 ms 10692 KB Output is correct
7 Correct 43 ms 10120 KB Output is correct
8 Correct 40 ms 9660 KB Output is correct
9 Correct 36 ms 9600 KB Output is correct
10 Correct 41 ms 10024 KB Output is correct
11 Correct 2 ms 3072 KB Output is correct
12 Correct 12 ms 7872 KB Output is correct
13 Correct 13 ms 7752 KB Output is correct
14 Correct 12 ms 7744 KB Output is correct
15 Correct 13 ms 7676 KB Output is correct
16 Correct 12 ms 7744 KB Output is correct
17 Correct 16 ms 7488 KB Output is correct
18 Correct 13 ms 7784 KB Output is correct
19 Correct 13 ms 7772 KB Output is correct
20 Correct 2 ms 3020 KB Output is correct
21 Correct 2 ms 3068 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Correct 14 ms 7744 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3064 KB Output is correct
2 Correct 3 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 3 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3036 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 3064 KB Output is correct
11 Correct 2 ms 3020 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Runtime error 4 ms 6072 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 94 ms 37188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -