Submission #1162685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162685		AlgorithmWarrior	Evacuation plan (IZhO18_plan)	C++20	100 / 100	435 ms	34504 KiB

plan

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=5e5+5;
int n,m;
struct EDGE{
    int u,v,w;
    bool operator<(EDGE ot){
        return w>ot.w;
    }
}edge[MAX];
struct muchie{
    int nod,w;
};
vector<muchie>G[MAX];
int k;
int cities[MAX];
int dist[MAX];
class cmp{
public:
    bool operator()(muchie a,muchie b){
        return a.w>b.w;
    }
};

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=m;++i){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
        auto [u,v,w]=edge[i];
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    cin>>k;
    for(i=1;i<=k;++i)
        cin>>cities[i];
}

void dijkstra(){
    priority_queue<muchie,vector<muchie>,cmp>pq;
    int i;
    for(i=1;i<=n;++i)
        dist[i]=INF;
    for(i=1;i<=k;++i){
        int nod=cities[i];
        dist[nod]=0;
        pq.push({nod,0});
    }
    while(!pq.empty()){
        auto [nd,dst] = pq.top();
        pq.pop();
        if(dst>dist[nd])
            continue;
        for(auto [vec,w] : G[nd])
            if(dist[vec]>dst+w){
                dist[vec]=dst+w;
                pq.push({vec,dist[vec]});
            }
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

struct DSU{
    int tata[MAX],rnk[MAX],len[MAX];
    int root(int nod){
        if(!tata[nod])
            return nod;
        return root(tata[nod]);
    }
    void uneste(int u,int v,int w){
        u=root(u);
        v=root(v);
        if(u!=v){
            if(rnk[u]<rnk[v])
                swap(u,v);
            if(rnk[u]==rnk[v])
                ++rnk[u];
            tata[v]=u;
            len[v]=w;
        }
    }
    int find_min_edge(int u,int v){
        int minim=INF;
        while(u!=v){
            if(rnk[u]>rnk[v])
                swap(u,v);
            minself(minim,len[u]);
            u=tata[u];
        }
        return minim;
    }
}dsu;

void kruskal(){
    int i;
    for(i=1;i<=m;++i){
        auto &[u,v,w] = edge[i];
        w=min(dist[u],dist[v]);
    }
    sort(edge+1,edge+m+1);
    for(i=1;i<=m;++i){
        auto [u,v,w] = edge[i];
        dsu.uneste(u,v,w);
    }
}

void process_queries(){
    int q;
    cin>>q;
    int i;
    for(i=1;i<=q;++i){
        int s,t;
        cin>>s>>t;
        cout<<dsu.find_min_edge(s,t)<<'\n';
    }
}

int main()
{
    read();
    dijkstra();
    kruskal();
    process_queries();
    return 0;
}

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