Submission #1045481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045481		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	329 ms	55204 KiB

plan

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

const int oo = 1e9;

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

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