Submission #519918

#	Time	Username	Problem	Language	Result	Execution time	Memory
519918		PiejanVDC	Dreaming (IOI13_dreaming)	C++17	18 / 100	94 ms	37188 KiB

dreaming

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23