Submission #1348121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1348121		SDAdzs1tg	Evacuation plan (IZhO18_plan)	C++20	0 / 100	6 ms	9796 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n, m, k, dist[maxn], id[maxn], ok[maxn], res;
int sz[maxn], par[maxn], ans[maxn];
multiset<int> st[maxn];
vector<pair<int, int>> adj[maxn];
struct tque{
    int v, w;
    bool operator < (const tque &c) const {
        return c.w < w;
    }
};
bool cmp(int a, int b) {
    return dist[a] > dist[b];
}
int findset(int u) {
    if(par[u] == u) return u;
    return par[u] = findset(par[u]);
}
void join(int u, int v) {
    u = findset(u);
    v = findset(v);
    if(u == v) return;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    for(auto i : st[v]) {
        if(st[u].find(i) != st[u].end()) {
            ans[i] = res;
            st[u].erase(i);
        }
        else st[u].insert(i);
    }
}
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("exit.inp", "r", stdin);
    freopen("exit.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        adj[u].push_back({v, l});
        adj[v].push_back({u, l});
    }
    cin >> k;
    priority_queue<tque> pq;
    for(int i = 1; i <= n; i++) {
        dist[i] = 1e18, id[i] = i;
        par[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= k; i++) {
        int x; cin >> x;
        dist[x] = 0;
        pq.push({x, 0});
    }
    while(!pq.empty()) {
        tque res = pq.top();
        pq.pop();
        if(res.w != dist[res.v]) continue;
        for(auto i : adj[res.v]) {
            if(dist[i.first] > dist[res.v] +  i.second) {
                dist[i.first] = dist[res.v] + i.second;
                pq.push({i.first, dist[i.first]});
            }
        }
    }
    int q; cin >> q;
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        st[x].insert(i);
        st[y].insert(i);
    }
    sort(id + 1, id + n + 1, cmp);
    for(int i = 1; i <= n; i++) {
        int x = id[i];
        res = dist[x];
        ok[x] = 1;
        for(auto j : adj[x]) {
            if(ok[j.first]) join(j.first, x);
        }
    }
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen("exit.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen("exit.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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