제출 #1124118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124118		boris_7	Evacuation plan (IZhO18_plan)	C++20	100 / 100	579 ms	55744 KiB

plan

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<pair<int,int>>>gp;
vector<vector<pair<int,int>>>tree;
vector<vector<int>>up,mi;
vector<int>par,sizes,tin,tout;
int timer = 0;

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

bool unions(int u,int v){
    u = get(u);
    v = get(v);
    if(u==v) return false;
    if(sizes[u]>sizes[v]) swap(u,v);
    sizes[v]+=sizes[u];
    par[u]=v;
    return true;
}



void dfs(int u,int p,int w){
    tin[u]=timer++;
    up[u][0]=p;
    mi[u][0]=w;
    for(int i=1;i<20;i++){
        up[u][i]=up[up[u][i-1]][i-1];
        mi[u][i]=min(mi[u][i-1],mi[up[u][i-1]][i-1]);
    }
    for(auto &i:tree[u]){
        if(i.first!=p){
            dfs(i.first,u,i.second);
        }
    }
    tout[u]=timer++;
}

bool isok(int u,int v){
    return tin[u]<=tin[v] && tout[u]>=tout[v];
}

int lca(int u,int v){
    if(isok(u,v)) return INT_MAX;
    int m = INT_MAX;
    for(int i = 19;i>=0;i--){
        if(!isok(up[u][i],v)){
            m = min(m,mi[u][i]);
            u=up[u][i];
        }
    }
    m = min(m,mi[u][0]);
    return m;
}

void solve() {
    int n,m;
    cin>>n>>m;
    up = mi = vector<vector<int>>(n,vector<int>(20));
    tree = gp = vector<vector<pair<int,int>>>(n);
    sizes = vector<int>(n,1);
    tin = tout = vector<int>(n);
    for(int i = 0;i<n;i++) par.push_back(i);
    for(int i = 0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        --u,--v;
        gp[u].push_back({v,w});
        gp[v].push_back({u,w});
    }
    set<pair<int,int>>pq;
    vector<int>d(n,INT_MAX);
    int q;
    cin>>q;
    while(q--){
        int u;
        cin>>u;
        --u;
        pq.insert({0,u});
        d[u]=0;
    }
    while(pq.size()){
        int u = (*pq.begin()).second;
        int dist = (*pq.begin()).first;
        pq.erase(pq.begin());
        if(d[u]!=dist) continue;
        for(pair<int,int> &i:gp[u]){
            if(dist+i.second<d[i.first]){
                d[i.first]=dist+i.second;
                pq.insert({d[i.first],i.first});
            }
        }
    }
    vector<pair<int,pair<int,int>>>we;
    for(int i = 0;i<n;i++){
        for(auto &j:gp[i]){
            j.second=min(d[i],d[j.first]);
            if(i<j.first){
                we.push_back({j.second,{i,j.first}});
            }
        }
    }
    sort(we.rbegin(),we.rend());
    for(pair<int,pair<int,int>> &i:we){
        if(unions(i.second.first,i.second.second)){
            tree[i.second.first].push_back({i.second.second,i.first}); 
            tree[i.second.second].push_back({i.second.first,i.first});
        }
    }
    dfs(0,0,d[0]);
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        --u,--v;
        cout<<min({d[u],d[v],lca(u,v),lca(v,u)})<<endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}

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