Submission #863075

#	Time	Username	Problem	Language	Result	Execution time	Memory
863075		Dec0Dedd	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1696 ms	51640 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+100;
const long long INF = 1e9;
const int K = 40;

typedef long long ll;
typedef pair<ll, ll> pii;

vector<pii> G[N];

ll d[N], n, m, k, q, ans[N], lq[N], rq[N], s[N], t[N];

struct dsu {
    vector<int> p;

    void init(int sz) {
        p.resize(sz+10);
        for (int i=0; i<sz+10; ++i) p[i]=i;
    }

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

    void mrg(int x, int y) {
        x=f(x), y=f(y);
        if (x == y) return;
        p[x]=y;
    }
};

void dijk(vector<int> s) {
    for (int i=0; i<=n; ++i) d[i]=INF;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (auto u : s) d[u]=0, pq.push({0, u});

    while (!pq.empty()) {
        pii x=pq.top(); pq.pop();
        int v=x.second;

        if (x.first > d[v]) continue;
        for (auto u : G[v]) {
            if (d[u.second] > d[v]+u.first) {
                d[u.second]=d[v]+u.first;
                pq.push({d[u.second], u.second});
            }
        }
    }
}

vector<pii> wghs;
void solve(int q) {
    for (int i=1; i<=q; ++i) wghs.push_back({(lq[i]+rq[i])/2, -i});

    for (int z=0; z<K; ++z) {
        dsu ds; ds.init(n+1);
        sort(wghs.begin(), wghs.end(), greater<pii>());

        for (auto &u : wghs) {
            if (u.second > 0) {
                int i=u.second;
                for (auto v : G[i]) {
                    if (d[v.second] >= u.first) ds.mrg(i, v.second);
                }
            } else {
                int i=-u.second;
                if (lq[i] > rq[i]) continue;
                if (ds.f(s[i]) == ds.f(t[i])) {
                    ans[i]=max(ans[i], u.first);
                    lq[i]=u.first+1;
                } else rq[i]=u.first-1;
                u.first=(lq[i]+rq[i])/2;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin>>n>>m;

    for (int i=1; i<=m; ++i) {
        ll a, b, w; cin>>a>>b>>w;
        G[a].push_back({w, b});
        G[b].push_back({w, a});
    } cin>>k;

    vector<int> g;
    for (int i=1; i<=k; ++i) {
        int x; cin>>x;
        g.push_back(x);
    } dijk(g);

    for (int i=1; i<=n; ++i) assert(d[i] < INF);

    cin>>q;
    for (int i=1; i<=n; ++i) wghs.push_back({d[i], i});
    for (int i=1; i<=q; ++i) {
        cin>>s[i]>>t[i];
        lq[i]=0, rq[i]=INF;
    } solve(q);

    for (int i=1; i<=q; ++i) cout<<ans[i]<<"\n";
}

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