Submission #1045452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045452		vjudge1	Evacuation plan (IZhO18_plan)	C++17	41 / 100	980 ms	524288 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

typedef long long ll;
typedef pair<ll,ll> pli;

const ll maxn=1e5+5;
const ll inf=1e18;

ll n,m,k,q,x,y,z,w,a[maxn];
vector<pair<ll,ll>> adj[maxn];
ll dist[maxn];
ll parent[maxn],id[maxn],sz[maxn];
set<ll> s[maxn];
ll ans[maxn];
bool mark[maxn];

void dijkstra()
{
    fill(dist+1,dist+n+1,inf);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    for (ll i=1;i<=k;i++)
    {
        dist[a[i]]=0;
        pq.push({0,a[i]});
    }
    while (!pq.empty())
    {
        ll u=pq.top().se;
        ll t=pq.top().fi;
        pq.pop();
        if (t>dist[u]) continue;
        for (auto e:adj[u])
        {
            ll v=e.fi;
            ll w=e.se;
            if (dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
}

ll find_set(ll u)
{
    if (u==parent[u]) return u;
    return parent[u]=find_set(parent[u]);
}

void union_set(ll u,ll v)
{
    u=find_set(u);
    v=find_set(v);
    if (u==v) return;
    parent[v]=u;
    for (ll x:s[v])
    {
        if (s[u].find(x)!=s[u].end())
        {
            s[u].erase(x);
            ans[x]=w;
        }
        else s[u].insert(x);
    }
}

bool cmp(ll a,ll b)
{
    return dist[a]>dist[b];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    cin>>k;
    for (ll i=1;i<=k;i++)
    {
        cin>>a[i];
    }
    dijkstra();
    cin>>q;
    for (ll i=1;i<=q;i++)
    {
        cin>>x>>y;
        s[x].insert(i);
        s[y].insert(i);
    }
    for (ll i=1;i<=n;i++)
    {
        id[i]=i;
        parent[i]=i;
    }
    sort(id+1,id+n+1,cmp);
    memset(mark,0,sizeof(mark));
    for (ll i=1;i<=n;i++)
    {
        x=id[i];
        mark[x]=true;
        w=dist[x];
        for (auto it:adj[x])
        {
            y=it.fi;
            if (mark[y]) union_set(x,y);
        }
    }
    for (ll i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}

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