Submission #785763

#	Time	Username	Problem	Language	Result	Execution time	Memory
785763		drdilyor	Dreaming (IOI13_dreaming)	C++17	47 / 100	102 ms	33864 KiB

dreaming

#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;

struct DSU {
    int n;
    vector<int> parent;
    vector<int> size;

    DSU(int n) : n(n), parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int get(int i) {
        return parent[i] == i ? i : parent[i] = get(parent[i]);
    }

    void merge(int v, int u) {
        v = get(v);
        u = get(u);
        if (u == v) return;
        if (size[v] < size[u]) swap(v, u);
        parent[u] = v;
        size[v] += size[u];
    }
};


int travelTime(int n, int m, int l, int a[], int b[], int t[]) {

    DSU cc(n);
    vector<vector<pair<int,int>>> aadj(n);
    for (int i = 0; i < m;i ++) {
        aadj[a[i]].push_back({b[i], t[i]});
        aadj[b[i]].push_back({a[i], t[i]});
        cc.merge(a[i], b[i]);
    }

    vector<vector<int>> comps(n);
    for (int i = 0; i < n;i++) {
        comps[cc.get(i)].push_back(i);
    }
    for (auto& i : comps)
        sort(i.begin(), i.end());

    vector<int> ccompress;
    for (int i = 0; i < n;i++) {
        if (cc.get(i) == i)
            ccompress.push_back(i);
    }
    sort(ccompress.begin(), ccompress.end());
    int k = ccompress.size();

    vector<vector<vector<pair<int,int>>>> adj(k);
    for (int i = 0; i < k; i++) {
        adj[i].resize(comps[ccompress[i]].size());
    }

    for (int i = 0; i <m; i++) {
        int u = a[i], v = b[i];
        auto& xs = comps[cc.get(u)];
        u = lower_bound(xs.begin(), xs.end(), u) - xs.begin();
        v = lower_bound(xs.begin(), xs.end(), v) - xs.begin();
        int tree_index = lower_bound(ccompress.begin(), ccompress.end(), cc.get(a[i])) - ccompress.begin();
        adj[tree_index][v].push_back({u, t[i]});
        adj[tree_index][u].push_back({v, t[i]});
    }

    vector<int> center(k);
    vector<int> mxdist(k);

    int inner_dist = 0;
    for (int tree = 0; tree < k; tree++) {
        auto dfs = [&](
                auto& dfs,
                int t,
                vector<int>& dist,
                int i, int p=-1, int w=0)->void{
            dist[i] = w;
            for (auto [e, ew] : adj[t][i]) {
                if (e == p) continue;
                dfs(dfs, t, dist, e, i, w + ew);
            }
        };
        int tn = adj[tree].size();

        vector<int> dist(tn);

        dfs(dfs, tree, dist, 0);
        int s1 = max_element(dist.begin(), dist.end()) - dist.begin();
        dfs(dfs, tree, dist, s1);
        int s2 = max_element(dist.begin(), dist.end()) - dist.begin();

        inner_dist = max(inner_dist, dist[s2]);
        vector<int> dist2(tn);
        dfs(dfs, tree, dist2, s2);
        for (int i = 0; i < tn; i++)
            dist[i] = max(dist[i], dist2[i]);

        center[tree] = min_element(dist.begin(), dist.end()) - dist.begin();

        dfs(dfs, tree, dist, center[tree]);
        sort(dist.begin(), dist.end(), greater());
        mxdist[tree] = dist[0];
    }
    assert(k == n - m);
    assert(k == 2);
    return max(inner_dist, mxdist[0] + mxdist[1] + l);
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23