Submission #545315

#	Time	Username	Problem	Language	Result	Execution time	Memory
545315		Ai7081	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1370 ms	41820 KiB

plan

#include <bits/stdc++.h>
using namespace std;
const bool debug = 1;

const int N = 100005;
const int inf = 1e9;

struct node{
    int dis, v;
    bool operator < (const node &o) const { return dis > o.dis; }
};

int n, m, q, a, b, c, dis[N], l[N], r[N], g[N];
pair<int, int> que[N];
vector<pair<int, int>> adj[N], ord;
vector<int> test[N];
priority_queue<node> pq;
bool mark[N];

int findg(int x) {
    if (g[x] == x) return x;
    return g[x] = findg(g[x]);
}

int main() {
    scanf(" %d %d", &n, &m);
    while (m--) {
        scanf(" %d %d %d", &a, &b, &c);
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    fill_n(dis, N, inf);
    scanf(" %d", &a);
    while (a--) {
        scanf(" %d", &b);
        pq.push({0, b});
        dis[b] = 0;
    }
    scanf(" %d", &q);
    for (int i=0; i<q; i++) scanf(" %d %d", &que[i].first, &que[i].second);

    while (!pq.empty()) {
        int v = pq.top().v, d = pq.top().dis;
        pq.pop();
        if (mark[v]) continue;
        mark[v] = true;
        for (auto [to, w] : adj[v]) {
            if (!mark[to] && dis[to] > d+w) {
                dis[to] = d+w;
                pq.push({dis[to], to});
            }
        }
    }
    for (int i=1; i<=n; i++) ord.push_back({dis[i], i});
    sort(ord.begin(), ord.end(), greater<pair<int, int>>());

    bool con = true;
    fill_n(r, N, n-1);
    while (con) {
        con = false;
        fill_n(test, N, vector<int>());
        fill_n(mark, N, false);
        for (int i=1; i<=n; i++) g[i] = i;
        for (int i=0; i<q; i++) {
            if (l[i] != r[i]) {
                test[(l[i]+r[i])/2].push_back(i);
                con = true;
            }
        }
        for (int i=0; i<n; i++) {
            int v = ord[i].second;
            mark[v] = true;
            for (auto [to, w] : adj[v]) if (mark[to]) g[findg(to)] = findg(v);
            for (auto it : test[i]) {
                if (findg(que[it].first) == findg(que[it].second)) r[it] = i;
                else l[it] = i+1;
            }
        }
    }
    for (int i=0; i<q; i++) printf("%d\n", ord[l[i]].first);
    return 0;
}

/*
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:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf(" %d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d", &a);
      |     ~~~~~^~~~~~~~~~~
plan.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %d", &b);
      |         ~~~~~^~~~~~~~~~~
plan.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf(" %d", &q);
      |     ~~~~~^~~~~~~~~~~
plan.cpp:40:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for (int i=0; i<q; i++) scanf(" %d %d", &que[i].first, &que[i].second);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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