Submission #334200

#	Time	Username	Problem	Language	Result	Execution time	Memory
334200		vipghn2003	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1432 ms	59152 KiB

plan

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;

const int N=1e5+5;
int n,m,d[N],s[N],t[N],l[N],r[N],res[N];
vector<pii>adj[N];
vector<int>query[5*N];

struct edge
{
    int u,v,w;
};
bool lf(edge a,edge b)
{
    return a.w<b.w;
}
vector<edge>e;

int p[N];

int Find(int x)
{
    if(x==p[x]) return x;
    return p[x]=Find(p[x]);
}

void Union(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return ;
    p[u]=v;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back(mp(v,w));
        adj[v].push_back(mp(u,w));
        e.push_back({u,v,w});
    }
    memset(d,127,sizeof d);
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    int k;
    cin>>k;
    while(k--)
    {
        int v;
        cin>>v;
        d[v]=0;
        pq.push(mp(0,v));
    }
    while(!pq.empty())
    {
        int u=pq.top().se;
        int dist=pq.top().fi;
        pq.pop();
        if(d[u]!=dist) continue;
        for(auto&x:adj[u])
        {
            int v=x.fi;
            int ndist=dist+x.se;
            if(d[v]>ndist)
            {
                d[v]=ndist;
                pq.push(mp(d[v],v));
            }
        }
    }
    for(int i=0;i<m;i++) e[i].w=min(d[e[i].u],d[e[i].v]);
    sort(e.begin(),e.end(),lf);
    //for(auto&x:e) cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>s[i]>>t[i];
        l[i]=0;
        r[i]=m-1;
    }
    for(int rep=0;rep<=20;rep++)
    {
        iota(p+1,p+n+1,1);
        for(int i=0;i<m;i++) query[i].clear();
        for(int i=1;i<=q;i++)
        {
            if(l[i]>r[i]) continue;
            int mid=(l[i]+r[i])/2;
            query[mid].push_back(i);
        }
        for(int i=m-1;i>=0;i--)
        {
            Union(e[i].u,e[i].v);
            for(auto&id:query[i])
            {
                if(Find(s[id])==Find(t[id]))
                {
                    res[id]=e[i].w;
                    l[id]=i+1;
                }
                else r[id]=i-1;
            }
        }
    }
    for(int i=1;i<=q;i++) cout<<res[i]<<'\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