Submission #767631

#	Time	Username	Problem	Language	Result	Execution time	Memory
767631		Trunkty	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1114 ms	103620 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m,k,q,curr;
vector<vector<int>> roads[100005];
int best[100005];
bool check[100005];
int ans[100005];

//

int root[100005];
set<int> vals[100005];

int findroot(int x){
    if(root[x]!=x){
        root[x] = findroot(root[x]);
    }
    return root[x];
}

void domerge(int x, int y){
    x = findroot(x);
    y = findroot(y);
    if(x==y){
        return;
    }
    if(vals[x].size()>vals[y].size()){
        swap(x,y);
    }
    for(int i:vals[x]){
        if(vals[y].find(i)!=vals[y].end()){
            ans[i] = curr;
            vals[y].erase(i);
        }
        else{
            vals[y].insert(i);
        }
    }
    vals[x].clear();
    root[x] = y;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        best[i] = 2e9;
        root[i] = i;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back({b,c});
        roads[b].push_back({a,c});
    }
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
    cin >> k;
    for(int i=1;i<=k;i++){
        int a;
        cin >> a;
        best[a] = 0;
        pq.push({0,a});
    }
    while(pq.size()>0){
        while(pq.size()>0 and check[pq.top()[1]]){
            pq.pop();
        }
        if(pq.size()==0){
            break;
        }
        int x = pq.top()[1];
        check[x] = true;
        pq.pop();
        for(vector<int> i:roads[x]){
            if(best[i[0]]>best[x]+i[1]){
                best[i[0]] = best[x]+i[1];
                pq.push({best[i[0]],i[0]});
            }
        }
    }
    vector<vector<int>> ord;
    for(int i=1;i<=n;i++){
        ord.push_back({best[i],i});
    }
    sort(ord.begin(),ord.end(),greater<vector<int>>());
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b;
        cin >> a >> b;
        vals[a].insert(i);
        vals[b].insert(i);
    }
    for(vector<int> i:ord){
        curr = i[0];
        for(vector<int> j:roads[i[1]]){
            if(best[j[0]]>=curr){
                domerge(i[1],j[0]);
            }
        }
    }
    for(int i=1;i<=q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

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