Submission #1130542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130542		I_FloPPed21	Evacuation plan (IZhO18_plan)	C++20	100 / 100	616 ms	28912 KiB

plan

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N=2e5+1;
int n,m;
vector<pair<int,int>>adj[N];
int dp[N];
vector<pair<int,int>>muchii;
int dsu[N];
struct query
{
    int a,b;
    int st,dr,mij,ind;
    int ans;
} qr[N];
int get(int x)
{
    int nod1=x;
    while(dsu[nod1]>0)
    {
        nod1=dsu[nod1];
    }

    while(dsu[x]>0)
    {
        int mid=dsu[x];
        dsu[x]=nod1;
        x=mid;
    }
    return x;
}
void unite(int x,int y)
{
    x=get(x),y=get(y);
    if(x==y)
        return;
    if(dsu[x]<dsu[y])
    {
        dsu[x]+=dsu[y];
        dsu[y]=x;
    }
    else
    {
        dsu[y]+=dsu[x];
        dsu[x]=y;
    }
}
void citeste()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        dp[i]=1e9+1;
    }
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        muchii.push_back({a,b});
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    priority_queue<pair<int,int>>pq;
    int k;
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        int nod;
        cin>>nod;
        dp[nod]=0;
        pq.push({-dp[nod],nod});
    }
    while(!pq.empty())
    {
        auto[x,nod]=pq.top();
        x=-x;
        pq.pop();
        for(auto [urm,cost]:adj[nod])
        {
            if(dp[urm]>dp[nod]+cost)
            {
                dp[urm]=dp[nod]+cost;
                pq.push({-dp[urm],urm});
            }
        }
    }
}
int q;
bool cmp(pair<int,int>x,pair<int,int>y)
{
    return min(dp[x.first],dp[x.second])>min(dp[y.first],dp[y.second]);
}
bool cq(query x,query y)
{
    return x.mij<y.mij;
}
bool final_cmp(query x,query y)
{
    return x.ind<y.ind;
}
void rezolva()
{
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>qr[i].a>>qr[i].b;
        qr[i].dr=muchii.size()-1;
        qr[i].st=0;
        qr[i].ind=i;
    }
    sort(muchii.begin(),muchii.end(),cmp);
    for(int bit=1; bit<=20; bit++)
    {
        for(int i=1; i<=q; i++)
        {
            qr[i].mij=(qr[i].st+qr[i].dr)/2;
        }
        for(int i=1; i<=n; i++)
            dsu[i]=-1;
        sort(qr+1,qr+q+1,cq);
        int point=0;
        for(int i=1; i<=q; i++)
        {

            while(point<=qr[i].mij&&point<muchii.size())
            {
                unite(muchii[point].first,muchii[point].second);
                point++;
            }
            if(get(qr[i].a)==get(qr[i].b))
            {
                qr[i].dr=qr[i].mij-1;
                qr[i].ans=min(dp[muchii[point-1].first],dp[muchii[point-1].second]);
            }
            else
            {
                qr[i].st=qr[i].mij+1;
            }
        }
    }
    sort(qr+1,qr+q+1,final_cmp);
    for(int i=1; i<=q; i++)
    {
        cout<<qr[i].ans<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    rezolva();
    return 0;
}

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