Submission #871967

#	Time	Username	Problem	Language	Result	Execution time	Memory
871967		8pete8	Evacuation plan (IZhO18_plan)	C++14	100 / 100	858 ms	51580 KiB

plan

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,pii>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,inf=1e18;
int n,m,dist[mxn+10],mx=0,pa[mxn+10],sz[mxn+10];
bitset<mxn+10>on;
vector<pii>adj[mxn+10],e;
int find(int u){return ((u==pa[u])?u:pa[u]=find(pa[u]));}
void merg(int a,int b){
    a=find(a),b=find(b);
    if(a==b)return;
    if(sz[a]>=sz[b]){
        pa[b]=a;
        sz[a]+=sz[b];
        return;
    }
    pa[a]=b;
    sz[b]+=sz[a];
}
int32_t main(){
    fastio
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    fill(dist,dist+mxn+5,inf);
    int c;cin>>c;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=0;i<c;i++){
        int a;cin>>a;
        pq.push({0,a});
        dist[a]=0;
    }
    while(!pq.empty()){
        int cur=pq.top().s;
        pq.pop();
        for(auto i:adj[cur]){
            if(dist[i.f]>dist[cur]+i.s){
                dist[i.f]=dist[cur]+i.s;
                pq.push({dist[i.f],i.f});
            }
        }
    }
    for(int i=1;i<=n;i++)e.pb({dist[i],i});
    sort(rall(e));
    int q;cin>>q;
    vector<pii>qry(q),b(q);
    vector<int>ans(q,inf);
    for(int i=0;i<q;i++){
        cin>>qry[i].f>>qry[i].s;
        b[i].f=0,b[i].s=n-1;
    }
    bool yes=true;
    int cnt=0;
    while(yes){
        cnt++;
        vector<pii>mid(q,{inf,inf});
        yes=false;
        for(int i=1;i<=n;i++)pa[i]=i,on[i]=false,sz[i]=1;
        for(int i=0;i<q;i++)if(b[i].f<=b[i].s)mid[i].f=(b[i].s+b[i].f)/2,mid[i].s=i,yes=true;
        sort(all(mid));
        int cur=0;
        for(int i=0;i<q;i++){
            if(mid[i].f==inf)continue;
            while(cur<=mid[i].f){
                on[e[cur].s]=true;
                for(auto i:adj[e[cur].s])if(on[i.f])merg(i.f,e[cur].s);
                cur++;
            }
            if(find(qry[mid[i].s].f)==find(qry[mid[i].s].s))b[mid[i].s].s=mid[i].f-1,ans[mid[i].s]=min(ans[mid[i].s],mid[i].f);
            else b[mid[i].s].f=mid[i].f+1;
        }
    }
    for(auto i:ans)cout<<e[i].f<<'\n';
}

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