Submission #1180955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180955		dion324	Dreaming (IOI13_dreaming)	C++20	0 / 100	1094 ms	14848 KiB

dreaming

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#include "dreaming.h"
using ll = long long;
using namespace std;

class DSU {
public:
    vector<int> parent, sz;
    DSU(ll x) {
        parent.resize(x);
        sz.resize(x, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    ll find_parent(ll x) {
        if (parent[x] != x)
            parent[x] = find_parent(parent[x]);
        return parent[x];
    }

    void unite(ll x, ll y) {
        ll parx = find_parent(x);
        ll pary = find_parent(y);
        if (parx == pary) return;
        if (sz[pary] > sz[parx]) swap(parx, pary);
        parent[pary] = parx;
        sz[parx] += sz[pary];
    }

    bool same(ll x, ll y) {
        return find_parent(x) == find_parent(y);
    }
};

vector<ll> dijkstra(ll src, vector<vector<pair<int, int>>> &adj) {
    vector<ll> dist(adj.size(), LLONG_MAX);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [weight, cur] = pq.top(); pq.pop();
        if (weight > dist[cur]) continue;
        for (auto [to, to_w] : adj[cur]) {
            if (dist[to] > to_w + dist[cur]) {
                dist[to] = to_w + dist[cur];
                pq.push({dist[to], to});
            }
        }
    }
    return dist;
}


 int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    if (M == 0) {
        cout << 2 * L << endl;
        return 0;
    }

    vector<vector<pair<int, int>>> adj(N);
    DSU dsu(N);

    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]);
        dsu.unite(A[i], B[i]);
    }

    map<int, vector<int>> components;
    for (int i = 0; i < N; ++i) {
        components[dsu.find_parent(i)].push_back(i);
    }

    vector<ll> sort_ecc;
    map<int, ll> ecc_by_root;

    for (auto &[root, nodes] : components) {
        ll min_ecc = LLONG_MAX;
        for (int u : nodes) {
            vector<ll> dist = dijkstra(u, adj);
            ll ecc = 0;
            for (int v : nodes) {
                if (dist[v] != LLONG_MAX) {
                    ecc = max(ecc, dist[v]);
                }
            }
            min_ecc = min(min_ecc, ecc);
        }
        ecc_by_root[root] = min_ecc;
        sort_ecc.push_back(min_ecc);
    }

    sort(sort_ecc.rbegin(), sort_ecc.rend());
    ll cur_ecc = sort_ecc[0];

    int dia_root = -1;
    for (auto &[root, ecc] : ecc_by_root) {
        if (ecc == cur_ecc) {
            dia_root = root;
            break;
        }
    }

    vector<int> &main_nodes = components[dia_root];
    int start = main_nodes[0];
    vector<ll> d1 = dijkstra(start, adj);
    int far1 = start;
    for (int v : main_nodes) {
        if (d1[v] != LLONG_MAX && d1[v] > d1[far1])
            far1 = v;
    }

    vector<ll> d2 = dijkstra(far1, adj);
    int far2 = far1;
    for (int v : main_nodes) {
        if (d2[v] != LLONG_MAX && d2[v] > d2[far2])
            far2 = v;
    }

    ll cur_dia = d2[far2];

    for (int i = 1; i < sort_ecc.size(); ++i) {
        cur_dia = max(cur_dia, cur_ecc + sort_ecc[i] + L);
    }

    cout << cur_dia << endl;
 }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:131:2: warning: control reaches end of non-void function [-Wreturn-type]
  131 |  }
      |  ^

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