Submission #878928

#	Time	Username	Problem	Language	Result	Execution time	Memory
878928		TahirAliyev	Evacuation plan (IZhO18_plan)	C++17	100 / 100	833 ms	91588 KiB

plan

#include <bits/stdc++.h>
using namespace std;


#define ll long long
#define oo 1e9
#define int ll
#define pii pair<int, int>

int n, m, q, k;
const int MAX = 5e5 + 5;

vector<int> source;
vector<pii> g[MAX];

int dist[MAX];
int par[MAX];
set<int> c[MAX]; 
int ans[MAX];

int find(int node){
    if(par[node] < 0) return node;
    return par[node] = find(par[node]);
}

void unite(int u, int v, int val){
    u = find(u), v = find(v);
    if(u == v) return;
    if(-par[u] < -par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;

    if(c[u].size() < c[v].size()) swap(c[u], c[v]);
    for(int a : c[v]){
        if(c[u].find(a) != c[u].end()){
            ans[a] = max(val, ans[a]);
            c[u].erase(a);
        }
        else{
            c[u].insert(a);
        }
    }
}

void djikstra(){
    for(int i = 1; i <= n; i++){
        dist[i] = oo;
    }
    set<pii> s;
    for(int a : source){
        dist[a] = 0;
        s.insert({0, a});
    }
    while(s.size()){
        int node = s.begin() -> second;
        s.erase(s.begin());
        for(pii to : g[node]){
            if(dist[to.first] > dist[node] + to.second){
                s.erase({dist[to.first], to.first});
                dist[to.first] = dist[node] + to.second;
                s.insert({dist[to.first], to.first});
            }
        }
    }
}

bool open[MAX];

signed main(){
    memset(par, -1, sizeof(par));
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, d; cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        int a; cin >> a;
        source.push_back(a);
    }
    djikstra();
    cin >> q;
    for(int i = 1; i <= q; i++){
        int a, b; cin >> a >> b;
        c[a].insert(i);
        c[b].insert(i);
    }
    vector<pii> v;
    for(int i = 1; i <= n; i++){
        v.push_back({dist[i], i});
    }
    sort(v.rbegin(), v.rend());
    for(auto node : v){
        for(pii to : g[node.second]){
            if(open[to.first]){
                unite(node.second, to.first, node.first);
            }
        }
        open[node.second] = 1;
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
}

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