Submission #387501

#	Time	Username	Problem	Language	Result	Execution time	Memory
387501		parsabahrami	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1002 ms	75296 KiB

plan

// I can feel death, can see its beady eyes
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e5 + 10;
int dp[N], ret[N], fr[N], to[N], w[N], M[N], ord[N], s[N], t[N], P[N], n, m, k;
vector<int> adj[N]; set<int> Q[N];

int Find(int v) {
    return !P[v] ? v : P[v] = Find(P[v]);
}

void Union(int u, int v, int x) {
    u = Find(u), v = Find(v);
    if (u == v) return;
    if (SZ(Q[u]) > SZ(Q[v])) swap(u, v);
    for (int id : Q[u]) {
        if (Q[v].find(id) != Q[v].end()) { ret[id] = x; Q[v].erase(id); }
        else Q[v].insert(id);
    }
    Q[u] = {}, P[u] = v;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &fr[i], &to[i], &w[i]);
        adj[fr[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    scanf("%d", &k); priority_queue<pii> pq;
    fill(dp, dp + N, 1e9);
    for (int i = 1; i <= k; i++) {
        int v; scanf("%d", &v);
        pq.push({dp[v] = 0, v});
    }
    while (SZ(pq)) {
        int v = pq.top().S; pq.pop();
        if (M[v]) continue;
        M[v] = 1;
        for (int id : adj[v]) {
            int u = fr[id] ^ to[id] ^ v; 
            if (dp[u] > dp[v] + w[id]) 
                dp[u] = dp[v] + w[id], pq.push({-dp[u], u});
        }
    }
    iota(ord + 1, ord + m + 1, 1);
    sort(ord + 1, ord + m + 1, [&] (int a, int b) { return min(dp[fr[a]], dp[to[a]]) > min(dp[fr[b]], dp[to[b]]); });
    int q; scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &s[i], &t[i]);
        Q[s[i]].insert(i), Q[t[i]].insert(i);
    }
    for (int _ = 1; _ <= m; _++) {
        int i = ord[_];
        Union(fr[i], to[i], min(dp[fr[i]], dp[to[i]]));
    }
    for (int i = 1; i <= q; i++) 
        printf("%d\n", ret[i]);
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         scanf("%d%d%d", &fr[i], &to[i], &w[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d", &k); priority_queue<pii> pq;
      |     ~~~~~^~~~~~~~~~
plan.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         int v; scanf("%d", &v);
      |                ~~~~~^~~~~~~~~~
plan.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
plan.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf("%d%d", &s[i], &t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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