Submission #951164

#	Time	Username	Problem	Language	Result	Execution time	Memory
951164		LOLOLO	Evacuation plan (IZhO18_plan)	C++14	100 / 100	774 ms	94396 KiB

plan

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 5e5 + 100;
vector <pair <int, int>> ed[N];
int f[N], used[N], sz[N], p[N], cnt[N], ans[N];
vector <pair <int, int>> edge;
vector < vector <int>> save;
stack <pair <int, int>> st;

int get(int a) {
    return p[a] ? get(p[a]) : a;
}

void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    st.push({a, b});
    sz[a] += sz[b];
    p[b] = a;
} 

bool same(int a, int b) {
    return get(a) == get(b);
}

void rollback(int tt) {
    while (sz(st) > tt) {
        pair <int, int> t = st.top();
        st.pop();
        sz[t.f] -= sz[t.s];
        p[t.s] = 0;
    }
}

int cur = -1;
void move(int l) {
    while (cur < l) {
        cur++;
        unite(save[cur][1], save[cur][2]);
        cnt[cur] = sz(st);
    }

    while (cur > l) {
        cur = l;
        rollback(cnt[l]);
    }
}

void bin(int l, int r, vector < vector <int>> &ask) {
    if (l > r || ask.empty())
        return;

    int m = (l + r)  / 2;
    move(m);
    vector < vector <int>> win, lose;
    for (auto x : ask) {
        if (same(x[0], x[1])) {
            ans[x[2]] = save[m][0];
            win.pb(x);
        } else {
            lose.pb(x);
        }
    }

    ask.clear();
    bin(l, m - 1, win);
    bin(m + 1, r, lose);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mem(f, 0x3f);

    int n, m;
    cin >> n >> m;

    fill(sz + 1, sz + 1 + n, 1);

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        ed[a].pb({b, w});
        ed[b].pb({a, w});
        edge.pb({a, b});
    }

    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

    int k;
    cin >> k;

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        f[x] = 0;
        pq.push({0, x});
    }

    while (sz(pq)) {
        auto t = pq.top();
        pq.pop();
        if (f[t.s] < t.f)
            continue;

        for (auto x : ed[t.s]) {
            if (f[x.f] > x.s + t.f) {
                f[x.f] = x.s + t.f;
                pq.push({f[x.f], x.f});
            }
        }
    }

    for (auto x : edge) {
        save.pb({min(f[x.f], f[x.s]), x.f, x.s});
    }

    sort(all(save), greater < vector <int>>());
    
    int q;
    cin >> q;

    vector < vector <int>> ask;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        ask.pb({s, t, i});
    }

    bin(0, m - 1, ask);
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}
/*
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