제출 #1048442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048442		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	332 ms	56220 KiB

plan

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

const int maxN = 1e5 + 5;
const int oo = 1e9;

int n, m, x, y, w, k, q, a[maxN], p[maxN], par[maxN], s[maxN], id[maxN];
vector<pair<int,int>> adj[maxN];
set<int> sz[maxN];
int dist[maxN];
bool mark[maxN];

bool cmp(int a, int b){
    return dist[a]>dist[b];
}

void dijstra(){
    for(int i = 1; i <= n; i++)
        dist[i] = oo;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    for(int i = 1; i <= k; i++){
        dist[a[i]] = 0;
        q.push({0, a[i]});
    }
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        if(mark[u]) continue;
        mark[u] = 1;
        for(auto e : adj[u]){
            int v = e.first;
            int w = e.second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}

int find_set(int u){
    if(u == par[u])
        return u;
    return par[u] = find_set(par[u]);
}

void union_set(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v)
        return ;
    if(s[u] < s[v])
        swap(u, v);
    par[v] = u;
    s[u] += s[v];
    for(auto it : sz[v]){
        if(sz[u].find(it) != sz[u].end()){
            sz[u].erase(it);
            p[it] = w;
        }
        else
            sz[u].insert(it);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    while(m--){
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    cin >> k;
    for(int i = 1; i <= k; i++)
        cin >> a[i];
    dijstra();
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> x >> y;
        sz[x].insert(i);
        sz[y].insert(i);
    }
    for(int i = 1; i <= n; i++){
        id[i] = i;
        par[i] = i;
        s[i] = 1;
    }
    sort(id + 1, id + n + 1, cmp);
    memset(mark, 0, sizeof(mark));
    for(int i = 1; i <= n; i++){
        x = id[i];
        mark[x] = 1;
        w = dist[x];
        for(auto it : adj[x]){
            y = it.first;
            if(mark[y])
                union_set(x, y);
        }
    }
    for(int i = 1; i <= q; i++)
        cout << p[i] << '\n';
    return 0;
}

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