Submission #1112628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112628		dosts	Evacuation plan (IZhO18_plan)	C++17	100 / 100	339 ms	43456 KiB

plan

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 5e2+1,inf = 1e16,MOD = 1e9+7; 
 
struct DSU {
    vi dad,change,sz;

    DSU(int nn) {
        dad.resize(nn+1);
        iota(dad.begin(),dad.end(),0);
        change.assign(nn+1,-1);
        sz.assign(nn+1,1);
    }

    int find(int x,int t) {
        if (change[x] == -1 || t < change[x]) return x;
        return find(dad[x],t);
    }

    void unite(int x,int y,int t) {
        int a = find(x,t);
        int b = find(y,t);
        if (a == b) return;
        if (sz[a] > sz[b]) swap(a,b);
        dad[a] = b;
        change[a] = t;
        sz[b]+=sz[a];
    }
};

void solve() { 
    int n,m;
    cin >> n >> m;
    vector<pii> edges[n+1];
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    int k;
    cin >> k;
    vi dist(n+1,inf);
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for (int i=1;i<=k;i++) {
        int c;
        cin >> c;
        pq.push({0,c});
        dist[c] = 0;
    }   
    while (!pq.empty()) {
        pii f= pq.top();
        pq.pop();
        if (dist[f.ss] < f.ff) continue;
        for (auto it : edges[f.ss]) {
            if (dist[it.ff] > f.ff+it.ss) {
                dist[it.ff] = f.ff+it.ss;
                pq.push({f.ff+it.ss,it.ff});
            }
        }
    }
    vector<int> ord(n+1);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin()+1,ord.end(),[&](int x,int y){
        return dist[x] > dist[y]; 
    });
    DSU dsu(n);
    vi active(n+1,0);
    for (int i=1;i<=n;i++) {
        int vert = ord[i];
        active[vert] = 1;
        for (auto it : edges[vert]) {
            if (active[it.ff]) dsu.unite(vert,it.ff,i);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x,y;
        cin >> x >> y;
        int l = 1;
        int r = n;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (dsu.find(x,m) == dsu.find(y,m)) r = m-1;
            else l = m+1;
        }
        cout << dist[ord[l]] << '\n';
    }
}  
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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