제출 #378594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378594		syl123456	Evacuation plan (IZhO18_plan)	C++17	100 / 100	629 ms	22620 KiB

plan

#include <bits/stdc++.h>
#define all(i) i.begin(), i.end()
#define rall(i) i.rbegin(), i.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
struct sq {
    int u, l, d, r;
    sq() = default;
    sq(int _u, int _l, int _d, int _r) : u(_u), l(_l), d(_d), r(_r) {}
};
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pi>> g(n);
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        --x, --y;
        g[x].emplace_back(y, z), g[y].emplace_back(x, z);
    }
    int k;
    cin >> k;
    vector<int> dis(n, -1);
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    for (int i = 0; i < k; ++i) {
        int x;
        cin >> x;
        --x;
        pq.emplace(0, x);
    }
    while (!pq.empty()) {
        int d = pq.top().first, i = pq.top().second;
        pq.pop();
        if (dis[i] != -1) continue;
        dis[i] = d;
        for (pi j : g[i]) if (dis[j.first] == -1)
            pq.emplace(d + j.second, j.first);
    }
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j){return dis[i] > dis[j] || dis[i] == dis[j] && i < j;});
    vector<pi> p(n, pi(-1, -1));
    vector<int> rank(n, -1);
    function<int(int)> find = [&](int i) {
        return p[i].first == -1 ? i : find(p[i].first);
    };
    for (int i : ord) {
        rank[i] = 0;
        int _t = dis[i];
        for (pi j : g[i]) if (~rank[j.first]) {
            int x = find(j.first);
            if (x == i) continue;
            if (rank[x] > rank[i]) p[i] = pi(x, _t), i = x;
            else if (rank[i] > rank[x]) p[x] = pi(i, _t);
            else p[x] = pi(i, _t), ++rank[i];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        int ans = min(dis[s], dis[t]);
        while (p[s].second >= ans) s = p[s].first;
        while (p[t].second >= ans) t = p[t].first;
        while (s != t) {
            ans = max(p[s].second, p[t].second);
            while (p[s].second >= ans) s = p[s].first;
            while (p[t].second >= ans) t = p[t].first;
        }
        cout << ans << '\n';
    }
}
/*
 * dijkstra min dis(i, g) for every i
 * sort 321, add, get persistent dsu, rank, record time
 * for q : find max k that s-t connected, every time max(p[s], p[t]) till s = t
 */

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In lambda function:
plan.cpp:43:81: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |     sort(all(ord), [&](int i, int j){return dis[i] > dis[j] || dis[i] == dis[j] && i < j;});

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