Submission #347064

#	Time	Username	Problem	Language	Result	Execution time	Memory
347064		andrii	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1404 ms	44788 KiB

plan

// -- //
#include <bits/stdc++.h>
#define pll pair<ll, ll>
#define x first
#define y second
using namespace std;
typedef long long ll;
const ll N = 1e5+228;
vector<pll> d[N];
vector<pll> edges;
ll aes[N];
bool is_aes[N];
ll was[N], wc=0;
ll len_aes[N];
ll qa[N], qb[N], ql[N], qr[N];
ll dsu[N];
ll _f(ll v){
    return dsu[v]==v?v:dsu[v]=_f(dsu[v]);
}
void _u(ll a, ll b){
    a=_f(a), b=_f(b);
    if(a==b) return;
    dsu[b]=a;
}
signed main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    ll n, mm, k, q;
    cin >> n >> mm;
    for(ll a, b, c, i=0;i<mm;i++){
        cin >> a >> b >> c;
        d[a].push_back({b, c});
        d[b].push_back({a, c});
        edges.push_back({a, b});
    }
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    cin >> k;
    for(ll i = 0;i<k;i++){
        cin >> aes[i];
        is_aes[aes[i]]=1;
        pq.push({0, aes[i]});
    }
    wc++;
    while(!pq.empty()){
        pll e = pq.top();pq.pop();
        while(was[e.y]==wc&&!pq.empty()){
            e=pq.top();pq.pop();
        }
        if(was[e.y]==wc) break;
        ll l = e.x, v = e.y;
        was[v]=wc;
        len_aes[v]=l;
        for(auto i : d[v]){
            if(was[i.x]!=wc) pq.push({l+i.y, i.x});
        }
    }
    ll max_len_aes=0;
    for(ll i = 1;i<=n;i++) max_len_aes=max(max_len_aes, len_aes[i]);
    cin >> q;
    vector<pair<pll, pll>> ev;
    for(ll i  =0;i<q;i++){
        cin >> qa[i] >> qb[i];
        if(is_aes[qa[i]]||is_aes[qb[i]]){
            ql[i]=-1, qr[i]=0;
        }else{
            ql[i]=0, qr[i]=max_len_aes;
            ll m = (ql[i]+qr[i])/2;
            ev.push_back({{m, 1}, {i, 0}});
        }
    }
    for(auto i : edges){
        ev.push_back({{min(len_aes[i.x], len_aes[i.y]), 0}, i});
    }
    for(ll QQ=0;QQ<40;QQ++){
        sort(begin(ev), end(ev), greater<pair<pll, pll>>());
        for(ll i =1;i<=n;i++) dsu[i]=i;
        vector<pair<pll, pll>> nev;
        for(auto j : ev){
            ll m = j.x.x, type=j.x.y, a=j.y.x, b=j.y.y;
            if(type==0){
                _u(a, b);
                nev.push_back(j);
            }else{
                bool can = (_f(qa[a])==_f(qb[a]));
                ll nm;
                if(can){
                    ql[a]=m;
                }else{
                    qr[a]=m-1;
                }
                nm = (ql[a]+qr[a])/2;
                if(ql[a]!=qr[a]) nev.push_back({{nm, 1}, {a, -1}});
            }
        }
        ev=nev;
    }
    for(ll i = 0;i<q;i++) cout<<ql[i]+1<<'\n';
}

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