oj.uz

Submission #785754

# Submission time Handle Problem Language Result Execution time Memory
785754 2023-07-17T14:37:03 Z drdilyor Dreaming (IOI13_dreaming) C++17
0 / 100
 92 ms 18288 KB 
#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();
        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];
        if (dist.size() > 1)
            inner_dist = max(inner_dist, dist[0] + dist[1]);
    }
    assert(k == n - m);
    return max(inner_dist, mxdist[0] + mxdist[1] + l);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 18288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 18288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 16744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 18288 KB Output isn't correct
2 Halted 0 ms 0 KB -