Submission #50847

#	Time	Username	Problem	Language	Result	Execution time	Memory
50847		Nicksechko	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1069 ms	45812 KiB

plan

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

const int MAXN = 200001;

int dp[MAXN];

using Pair = pair<int, int>;

set <Pair> s;

vector<pair<int, int> > gid[MAXN];
vector<int> g[MAXN];

vector<pair<int, int>> e[MAXN];

constexpr int INF = 1 << 30;

void upd(int x, int y) {
    if (dp[x] < y) {
        return;
    }

    s.erase({ dp[x], x });
    dp[x] = y;
    s.emplace(y, x);
}

int dist(int a, int b) {
    int l = 0, r = min(gid[a].size(), gid[b].size());
    while (l < r) {
        int m = (l + r) / 2;
        if (gid[a][m] == gid[b][m]) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    int ans = 0;
    for (int i = max(l - 1, 0); i <= l; ++i) {
        for (int j = max(l - 1, 0); j <= l; ++j) {
            if (gid[a][i].first == gid[b][j].first) {
                ans = max(ans, min(gid[a][i].second, gid[b][j].second));
            }
        }
    }

    return ans;
}

vector <pair<int, pair<int, int>>> edges;

int main() {
#ifdef PAUNSVOKNO
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        g[i] = { i };
        gid[i] = {{i, INF} };
    }
    
    fill(dp + 1, dp + n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        e[a].emplace_back(b, w);
        e[b].emplace_back(a, w);
    }

    int cities;
    cin >> cities;
    for (int i = 0; i < cities; ++i) {
        int v;
        cin >> v;
        upd(v, 0);
    }

    while (!s.empty()) {
        int v = s.begin()->second;
        s.erase(s.begin());

        for (auto ed : e[v]) {
            upd(ed.first, dp[v] + ed.second);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (auto ed : e[i]) {
            if (ed.first > i) {
                edges.push_back({ min(dp[i], dp[ed.first]), {i, ed.first} });
            }
        }
    }

    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());

    for (auto& edge : edges) {
        int v = edge.second.first;
        int u = edge.second.second;
        int gv = gid[v].back().first;
        int gu = gid[u].back().first;

        if (gv != gu) {
            if (g[gv].size() > g[gu].size()) {
                swap(gv, gu);
            }

            for (int ver : g[gv]) {
                gid[ver].emplace_back(gu, edge.first);
                g[gu].push_back(ver);
            }

            g[gv].clear();
        }
    }

    for (int i = 1; i <= n; ++i) {
        reverse(gid[i].begin(), gid[i].end());
    }

    ll sum = 0;

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        cout << dist(a, b) << endl;
    }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:129:8: warning: unused variable 'sum' [-Wunused-variable]
     ll sum = 0;
        ^~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46