Submission #190915

#	Time	Username	Problem	Language	Result	Execution time	Memory
190915		godwind	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1528 ms	41932 KiB

plan

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;


#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
random_device rnd;
 
template<typename T> void shuffle(vector< T > &v) {
    for (int i = 1; i < (int)v.size(); ++i) {
        swap(v[rnd() % i], v[i]);
    }
    for (int i = (int)v.size() - 1; i; --i) {
        swap(v[rnd() % i], v[i]);
    }
}

const int N = 100 * 1000 + 228;
const int INF = 1e9 + 228;

int n, m, k, q;
int left[N], right[N], middle[N];
int dist[N], s[N], t[N];
vector<int> order;
vector<int> list[N];
vector< pair<int, int> > g[N];

void GO(vector<int> lalalala) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    for (int i : lalalala) {
        dist[i] = 0;
    }
    priority_queue< pair<int, int> > st;
    for (int i : lalalala) {
        st.push({0, i});
    }
    while (!st.empty()) {
        pair<int, int> p = st.top();
        st.pop();
        int v = p.second;
        for (pair<int, int> go : g[v]) {
            int to = go.first, w = go.second;
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                st.push({-dist[to], to});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        order.push_back(i);
    }
    sort(order.begin(), order.end(), [&] (int i, int j) {
        return dist[i] > dist[j];
    });
}

int p[N], sz[N];


void init() {
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        sz[i] = 1;
    }
}
int getp(int v) {
    if (v == p[v]) return v;
    p[v] = getp(p[v]);
    return p[v];
}
void join(int u, int v) {
    u = getp(u);
    v = getp(v);
    if (u != v) {
        if (sz[u] < sz[v]) {
            p[u] = v;
            sz[v] += sz[u];
        } else {
            p[v] = u;
            sz[u] += sz[v];
        }
    }
}
bool con(int u, int v) {
    return getp(u) == getp(v);
}

bool on[N], done[N];

void proceed() {
    for (int i = 1; i <= n; ++i) {
        on[i] = 0;
    }
    for (int i = 0; i < q; ++i) {
        done[i] = 0;
    }
    init();
    for (int i = 0; i < n; ++i) {
        int v = order[i];
        on[v] = 1;
        for (pair<int, int> to : g[v]) {
            if (on[to.first]) {
                join(v, to.first);
            }
        }
        for (int id : list[i + 1]) {
            if (con(s[id], t[id])) {
                done[id] = 1;
            }
        }
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    cin >> k;
    vector<int> bad(k);
    for (int i = 0; i < k; ++i) {
        cin >> bad[i];
    }
    GO(bad);
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> s[i] >> t[i];
    }
    for (int i = 0; i < q; ++i) {
        left[i] = 0;
        right[i] = n;
    }
    bool oke = 0;
    while (!oke) {
        for (int i = 0; i <= n; ++i) {
            list[i].clear();
        }
        for (int i = 0; i < q; ++i) {
            middle[i] = (left[i] + right[i]) >> 1;
            list[middle[i]].push_back(i);
        }
        proceed();
        for (int i = 0; i < q; ++i) {
            if (done[i]) {
                right[i] = middle[i];
            } else {
                left[i] = middle[i];
            }
        }
        oke = 1;
        for (int i = 0; i < q; ++i) {
            if (right[i] - left[i] > 1) {
                oke = 0;
                break;
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << dist[order[right[i] - 1]] << '\n';
    }
    return 0;
}
// RU_023


/*

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