Submission #868822

#	Time	Username	Problem	Language	Result	Execution time	Memory
868822		12345678	Evacuation plan (IZhO18_plan)	C++17	100 / 100	730 ms	41884 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, m, u, v, w, k, x, q, s[nx], t[nx], mn[nx], dsu[nx], l[nx], r[nx], cnt=18;
vector<pair<int, int>> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> cq[nx];

int find(int x)
{
    if (x==dsu[x]) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    for (int i=1; i<=n; i++) mn[i]=1e9;
    cin>>k;
    for (int i=1; i<=k; i++) cin>>x, mn[x]=0, pq.push({0, x});
    while (!pq.empty())
    {
        auto [cw, cl]=pq.top();
        pq.pop();
        for (auto [nl, nw]:d[cl]) if (cw+nw<mn[nl]) mn[nl]=cw+nw, pq.push({cw+nw, nl});
    }
    vector<pair<int, int>> st;
    for (int i=1; i<=n; i++) st.push_back({mn[i], i});
    sort(st.begin(), st.end());
    reverse(st.begin(), st.end());
    cin>>q;
    for (int i=0; i<q; i++) cin>>s[i]>>t[i], l[i]=1, r[i]=n;
    while (cnt--)
    {
        vector<bool> open(n+1);
        for (int i=1; i<=n; i++) cq[i].clear(), dsu[i]=i;
        for (int i=0; i<q; i++) 
        {
            if (l[i]==r[i]) continue;
            cq[(l[i]+r[i])/2].push_back(i);
        }
        for (int i=1; i<=n; i++)
        {
            u=st[i-1].second;
            open[u]=1;
            for (auto [v, w]:d[u])
            {
                if (!open[v]) continue;
                int pu=find(u), pv=find(v);
                if (pu!=pv) dsu[pu]=pv;
            }
            for (auto idx:cq[i])
            {
                if (open[s[idx]]&&open[t[idx]]&&find(s[idx])==find(t[idx])) r[idx]=i;
                else l[idx]=i+1;
            }
        }
    }
    for (int i=0; i<q; i++) cout<<st[l[i]-1].first<<'\n';
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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