Submission #972755

#	Time	Username	Problem	Language	Result	Execution time	Memory
972755		blackslex	Evacuation plan (IZhO18_plan)	C++17	100 / 100	753 ms	43284 KiB

plan

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using tp = tuple<int, int, int>;

int n, m, k, q;

int main() {
    scanf("%d %d", &n, &m);
    vector<tp> u(m);
    vector<vector<pii>> v(n + 5, vector<pii>());
    for (auto &[z, x, y]: u) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
    scanf("%d", &k);
    vector<int> g(k), d(n + 5, 1e9);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (auto &e: g) scanf("%d", &e), pq.emplace(d[e] = 0, e);
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) if (d[tn] > d[nn] + td) pq.emplace(d[tn] = d[nn] + td, tn);
    }
    set<int> s;
    map<int, int> mp;
    vector<int> pos(n + 5);
    for (int i = 1; i <= n; i++) s.emplace(d[i]);
    int idx = 0;
    for (auto e: s) mp[e] = ++idx, pos[idx] = e;
    vector<vector<pii>> cu(idx + 5);
    for (auto &[z, x, y]: u) cu[mp[min(d[x], d[y])]].emplace_back(x, y);
    scanf("%d", &q);
    vector<pii> cq(q);
    for (auto &[x, y]: cq) scanf("%d %d", &x, &y);
    vector<int> l(q, 1), r(q, idx), mid(q);
    while (1) {
        vector<vector<int>> t(idx + 5, vector<int>());
        bool ck = 1;
        for (int i = 0; i < q; i++) if (l[i] <= r[i]) mid[i] = (l[i] + r[i]) >> 1, t[mid[i]].emplace_back(i), ck = 0;
        if (ck) break;
        vector<int> par(n + 5); iota(par.begin(), par.end(), 0);
        function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
        for (int i = idx; i >= 1; i--) {
            for (auto &[x, y]: cu[i]) par[fset(x)] = fset(y);
            for (auto &e: t[i]) {
                if (fset(cq[e].first) != fset(cq[e].second)) r[e] = mid[e] - 1;
                else l[e] = mid[e] + 1;
            }
        }
    }
    for (auto &e: r) printf("%d\n", pos[e]);
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:13:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for (auto &[z, x, y]: u) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
plan.cpp:17:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     for (auto &e: g) scanf("%d", &e), pq.emplace(d[e] = 0, e);
      |                      ~~~~~^~~~~~~~~~
plan.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
plan.cpp:32:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     for (auto &[x, y]: cq) scanf("%d %d", &x, &y);
      |                            ~~~~~^~~~~~~~~~~~~~~~~

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