Submission #378623

#	Time	Username	Problem	Language	Result	Execution time	Memory
378623		balbit	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1256 ms	26068 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(), x.end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 1e5+5;
vector<pii> g[maxn];
ll d[maxn], ans[maxn];
int par[maxn]; bool done[maxn];

int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}

void mrg(int a, int b) {
    if (!done[b]) return;
    a = find(a); b = find(b); par[a] = b;
//    done[b] = 1;
}

bool can(int a, int b) {
    return done[a] && done[b] && find(a) == find(b);
}

struct chunk{
    int l,r;
    vector<pair<int, pii> > v;
};

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
    int n,m; cin>>n>>m;
    REP(i,m) {
        int a,b,w; cin>>a>>b>>w; --a; --b;
        g[a].pb({b,w});
        g[b].pb({a,w});
    }
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    vector<int> dg;
    int nbad; cin>>nbad;
    memset(d, 0x3f, sizeof d);
    REP(i,nbad) {
        int x; cin>>x; x--; dg.pb(x);
        d[x] = 0;
        pq.push({0,x});
    }
    while (!pq.empty() ) {
        int w = pq.top().f, v = pq.top().s; pq.pop();
        if (d[v] != w) continue;
        for (pii u : g[v]) {
            if (d[u.f] > d[v] + u.s) {
                d[u.f] = d[v] + u.s;
                pq.push({d[u.f], u.f});
            }
        }
    }
    vector<pii> here;
    chunk gogo; gogo.l=0, gogo.r = n-1;
    REP(i,n) {
        here.pb({d[i], i});
        bug(i, d[i]);
    }
    int qu; cin>>qu;
    REP(i,qu) {
        int a,b; cin>>a>>b;
        gogo.v.pb({i, {a-1, b-1}});
    }
    sort(ALL(here)); reverse(ALL(here));
    queue<chunk> q;
    q.push(gogo);
    int now = 10000000;
    while (!q.empty()){
        chunk c = q.front(); q.pop();
        if (c.l == c.r) {
            for (auto u : c.v) {
                ans[u.f] = here[c.l].f;
            }
            continue;
        }
        int mid = ((c.l) + (c.r)) >>1;
        if (now > mid) {
            now = -1;
            REP(i,n) {
                par[i] = i; done[i] = 0;
            }
        }
        while (now<mid) {
            ++now;
            int v = here[now].s; done[v] = 1;
            for (pii u : g[v]) {
                mrg(v, u.f);
            }
        }
        chunk lc, rc; lc.l = c.l, lc.r = mid; rc.l=mid+1, rc.r=c.r;
        for (auto u : c.v) {
            if (can(u.s.f, u.s.s)) {
                lc.v.pb(u);
            }else{
                rc.v.pb(u);
            }
        }
        if (!lc.v.empty()) q.push(lc);
        if (!rc.v.empty()) q.push(rc);
    }

    REP(i,qu) {
        cout<<ans[i]<<endl;
    }

}

/*
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