Submission #157710

#	Time	Username	Problem	Language	Result	Execution time	Memory
157710		brcode	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1800 ms	56048 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e5+5;
priority_queue<pair<int,int>> pq;
int par[MAXN];
int sz[MAXN];
int depth[MAXN];
int lift[MAXN][25];
int dp[MAXN];
int npp[MAXN];
vector<pair<int,int>> v1[MAXN];
vector<pair<int,int>> v2[MAXN];
vector<pair<int,pair<int,int>>> edges;
int lift2[MAXN][25];
int n,m;
int findpar(int a){
    if(par[a] == a){
        return a;
    }
    return par[a] = findpar(par[a]);
}
void merge(int a,int b){
    a = findpar(a);
    b = findpar(b);
    if(a == b){
        return;
    }
    if(sz[a]<sz[b]){
        swap(a,b);
    }
    par[b] = a;
    sz[a] += sz[b];
}
void dfs(int curr,int p,int lvl){

    depth[curr] = lvl;
    lift[curr][0] = p;

    for(auto x:v2[curr]){
        if(x.first!=p){
            lift2[x.first][0] = x.second;
            dfs(x.first,curr,lvl+1);
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int i=20;i>=0;i--){
        if(lift[a][i]!=-1 && depth[lift[a][i]]>=depth[b]){
            a= lift[a][i];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=20;i>=0;i--){
        if(lift[a][i]!=-1 && lift[a][i]!=lift[b][i]){
            a=lift[a][i];
            b = lift[b][i];
        }
    }
    return lift[a][0];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        dp[i] = 1e9;
        par[i] = i;
        sz[i] = 1;
    }
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        v1[x].push_back(make_pair(y,w));
        v1[y].push_back(make_pair(x,w));
    }
    int nppcount;
    cin>>nppcount;
    for(int i=1;i<=nppcount;i++){
        cin>>npp[i];
        pq.push(make_pair(0,npp[i]));
        dp[npp[i]] = 0;
    }
    while(!pq.empty()){
        auto hold = pq.top();
        int w = -1*hold.first;
        int curr = hold.second;
        pq.pop();
        for(auto x:v1[curr]){
            if(dp[curr]+x.second<dp[x.first]){
                dp[x.first] = dp[curr]+x.second;
                pq.push(make_pair(-dp[x.first],x.first));
            }
        }
    }
    //cout<<dp[9]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<v1[i].size();j++){

            edges.push_back(make_pair(min(dp[v1[i][j].first],dp[i]),make_pair(i,v1[i][j].first)));
        }
    }
    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());
    for(auto x:edges){
        int w = x.first;
        int a = x.second.first;
        int b = x.second.second;
        if(findpar(a)!=findpar(b)){
            merge(a,b);
            v2[a].push_back(make_pair(b,w));
            v2[b].push_back(make_pair(a,w));
            //cout<<a<<" "<<b<<" "<<w<<endl;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=20;j++){
            lift[i][j] = -1;
            lift2[i][j] = 1e9;
        }
    }
    dfs(1,-1,0);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(lift[i][j-1]==-1){
                lift[i][j] = -1;
            }else{
                lift[i][j] = lift[lift[i][j-1]][j-1];
            }

        }
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(lift2[i][j-1]==1e9){
                lift2[i][j] = 1e9;
            }else{
                lift2[i][j] = min(lift2[lift[i][j-1]][j-1],lift2[i][j-1]);
            }

        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        int c = lca(a,b);
       // cout<<c<<endl;
        int ans = 1e9;
        for(int j=20;j>=0;j--){
            if(lift[a][j]!=-1 && depth[lift[a][j]]>=depth[c]){
                ans = min(ans,lift2[a][j]);
                a =lift[a][j];
            }
        }
        for(int j=20;j>=0;j--){
            if(lift[b][j]!=-1 && depth[lift[b][j]]>=depth[c]){
                ans=min(ans,lift2[b][j]);
                b= lift[b][j];
            }
        }
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:91:13: warning: unused variable 'w' [-Wunused-variable]
         int w = -1*hold.first;
             ^
plan.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v1[i].size();j++){
                     ~^~~~~~~~~~~~~

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