Submission #860786

#	Time	Username	Problem	Language	Result	Execution time	Memory
860786		alexdd	Evacuation plan (IZhO18_plan)	C++17	100 / 100	593 ms	37784 KiB

plan

#include<bits/stdc++.h>
using namespace std;

/*ifstream fin("evacplan.in");
ofstream fout("evacplan.out");
#define cin fin
#define cout fout*/

const int INF = 1e9;
int n,m,k,q,pas;
int father[100005];
int rez[100005];
bool done[100005];
vector<pair<pair<int,int>,int>> qrys[100005];
int dist[100005];
pair<int,int> v[100005];
vector<pair<int,int>> con[100005];
priority_queue<pair<int,int>> pq;
void dijkstra()
{
    while(!pq.empty())
    {
        int nod = pq.top().second;
        int cdist = -pq.top().first;
        pq.pop();
        if(dist[nod]!=cdist)
            continue;
        for(auto x:con[nod])
        {
            if(dist[x.first] > dist[nod] + x.second)
            {
                dist[x.first] = dist[nod] + x.second;
                pq.push({-dist[x.first], x.first});
            }
        }
    }
}

int gas(int x)
{
    if(father[x]!=x)
        father[x]=gas(father[x]);
    return father[x];
}
void unite(int x, int y)
{
    x = gas(x);
    y = gas(y);
    if(x==y)
        return;
    if((int)qrys[x].size() < (int)qrys[y].size())
        swap(x,y);
    for(auto z:qrys[y])
    {
        if(gas(z.first.second)==x && !done[z.second])
        {
            done[z.second]=1;
            rez[z.second]=pas;
        }
        else
            qrys[x].push_back(z);
    }
    qrys[y].clear();
    father[y]=x;
}

signed main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int a,b,w;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>w;
        con[a].push_back({b,w});
        con[b].push_back({a,w});
    }
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        cin>>a;
        dist[a]=0;
        pq.push({0,a});
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        v[i] = {dist[i], i};
        father[i]=i;
    }
    sort(v+1,v+1+n);
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        if(a==b)
        {
            rez[i] = dist[a];
        }
        else
        {
            qrys[a].push_back({{a,b},i});
            qrys[b].push_back({{b,a},i});
        }
    }
    for(int i=n;i>0;i--)
    {
        pas = v[i].first;
        int x = v[i].second;
        for(auto adj:con[x])
            if(dist[adj.first] >= dist[x])
                unite(x, adj.first);
    }
    for(int i=0;i<q;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

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