Submission #378620

#	Time	Username	Problem	Language	Result	Execution time	Memory
378620		2qbingxuan	Evacuation plan (IZhO18_plan)	C++14	100 / 100	886 ms	33620 KiB

plan

#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
using ll = int64_t;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const int maxn = 100025, inf = 1e9;
const ll INF = 1e18;

int dis[maxn];
vector<pair<int,int>> g[maxn];

namespace dsu {

int pa[maxn];
set<int> st[maxn];
int ans[maxn];
void init(int n) { for (int i = 0; i < n; i++) pa[i] = i; }
int anc(int x) { return x==pa[x] ? x : pa[x]=anc(pa[x]); }
void join(int x, int y, int d) {
    if ((x=anc(x)) == (y=anc(y))) return;
    if (st[x].size() < st[y].size()) swap(x, y);
    for (int qid: st[y]) {
        if (st[x].count(qid)) {
            st[x].erase(qid);
            ans[qid] = d;
            debug(qid, d);
        } else {
            st[x].insert(qid);
        }
    }
    pa[y] = x;
    st[y].clear();
}

}

bool alive[maxn];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }
    fill(dis, dis+n, inf);
    min_heap<pair<int,int>> pq;
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int g;
        cin >> g;
        --g;
        pq.emplace(dis[g] = 0, g);
    }
    while (!pq.empty()) {
        auto [d, i] = pq.top(); pq.pop();
        if (dis[i] != d) continue;
        for (auto [j, w]: g[i]) {
            if (dis[j] > dis[i] + w)
                pq.emplace(dis[j] = dis[i] + w, j);
        }
    }

    dsu::init(n);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        dsu::st[s].insert(i);
        dsu::st[t].insert(i);
    }

    vector<int> id(n);
    iota(all(id), 0);
    sort(all(id), [](int a, int b){ return dis[a] > dis[b]; });
    for (int i: id) {
        alive[i] = true;
        for (auto [j, w]: g[i]) {
            if (alive[j])
                dsu::join(i, j, dis[i]);
        }
    }
    for (int i = 0; i < q; i++)
        cout << dsu::ans[i] << '\n';
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
 */

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         auto [d, i] = pq.top(); pq.pop();
      |              ^
plan.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |         for (auto [j, w]: g[i]) {
      |                   ^
plan.cpp:96:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |         for (auto [j, w]: g[i]) {
      |                   ^

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