Submission #1055308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055308		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	391 ms	62628 KiB

plan

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define task "D"
#define pa pair < int, int >
#define fi first
#define se second

const int N = 2e5 + 1;
const int INF = 1e18;
const int mod = 1e9 + 3;
int n, m, q, k, cur = 0;
int a[N], d[N], p[N], ans[N];
set < int > se[N];
vector < pa > g[N];

void dijkstra() {
    fill(d + 1, d + N - 1, LLONG_MAX);
    cin >> k;
    set < pa > st;
    for(int i = 0; i < k; i++){
        int x;
        cin >> x;
        d[x] = 0;
        st.insert({0, x});
    }
    while(!st.empty()){
        int v = st.begin()->se;
        st.erase(st.begin());

        for(auto [to, w] : g[v]){
            if (d[to] > d[v] + w){
                st.erase({d[to], to});
                d[to] = d[v] + w;
                st.insert({d[to], to});
            }
        }
    }
}

int get(int v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
}

void merge(int v, int u) {
    v = get(v);
    u = get(u);
    if (v == u) return;

    p[u] = v;
    if(se[v].size() < se[u].size()){
        se[v].swap(se[u]);
    }

    for(auto i : se[u]){
        if(se[v].find(i) == se[v].end()){
            se[v].insert(i);
        }
        else{
            ans[i] = cur;
            se[v].erase(i);
        }
    }
    se[u].clear();
}

bool cmp(int x, int y){
    return d[x] > d[y];
}

void read(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    dijkstra();
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        se[s].insert(i);
        se[t].insert(i);
    }

    for(int i = 1; i <= n; ++i){
        a[i] = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++i){
        p[i] = i;
    }
    for(int i = 1; i <= n; ++i) {
        cur = d[a[i]];
        for(auto [to, w] : g[a[i]]){
            if(d[to] >= d[a[i]]){
                merge(a[i], to);
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    int t = 1;
    while(t--){
        read();
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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