Submission #308723

#	Time	Username	Problem	Language	Result	Execution time	Memory
308723		aZvezda	Evacuation plan (IZhO18_plan)	C++14	22 / 100	5 ms	1792 KiB

plan

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 2e3 + 110;

struct State {
    vector<pair<ll, pair<ll, ll> > > arr;
    ll l, r;
};

State curr[MAX_N], nxt[MAX_N];
ll dist[MAX_N];
vector<pair<ll, pair<ll, ll> > > edges;
vector<pair<ll, ll> > g[MAX_N];

void dij(vector<ll> &st) {
    fill_n(dist, MAX_N, mod);
    priority_queue<pair<ll, ll> > pq;
    for(auto it : st) {
        dist[it] = 0;
        pq.push({0, it});
    }
    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        if(curr.first != dist[curr.second]) {continue;}
        for(auto it : g[curr.second]) {
            if(curr.first + it.second < dist[it.first]) {
                dist[it.first] = curr.first + it.second;
                pq.push({curr.first + it.second, it.first});
            }
        }
    }
}

ll par[MAX_N], sz[MAX_N];

void init(ll n) {
    for(ll i = 1; i <= n; i ++) {
        par[i] = i;
        sz[i] = 1;
    }
}

ll find(ll x) {
    if(x == par[x]) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void merge(ll x, ll y) {
    x = find(x); y = find(y);
    if(x == y) {return;}
    if(sz[x] < sz[y]) {swap(x, y);}
    par[y] = x;
    sz[x] += sz[y];
}

ll ans[MAX_N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n, m;
    cin >> n >> m;
    for(ll i = 0; i < m; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        edges.push_back({-1, {a, b}});
    }
    ll k;
    cin >> k;
    vector<ll> st;
    for(ll i = 0; i < k; i ++) {
        ll a;
        cin >> a;
        st.push_back(a);
    }
    dij(st);
    for(auto &it : edges) {
        it.first = min(dist[it.second.first], dist[it.second.second]);
    }
    edges.push_back({mod, {1, 1}}); //TODO
    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());
    ll q;
    cin >> q;
    ll l = 0, r = m;
    ll md = (l + r) / 2ll;

    curr[md].l = l, curr[md].r = r;
    for(ll i = 0; i < q; i ++) {
        ll a, b;
        cin >> a >> b;
        curr[md].arr.push_back({i, {a, b}});
    }
    while(true) {
        init(n);
        for(ll i = 0; i <= m; i ++) {
            nxt[i].arr.resize(0);
        }

        bool flag = false;
        for(ll md = 0; md <= m; md ++) {
            merge(edges[md].second.first, edges[md].second.second);
            for(auto &it : curr[md].arr) {
                if(curr[md].l == curr[md].r - 1) {
                    ans[it.first] = edges[curr[md].r].first;
                } else {
                    flag = true;
                    if(find(it.second.first) == find(it.second.second)) {
                        nxt[(curr[md].l + md) / 2ll].arr.push_back(it);
                        nxt[(curr[md].l + md) / 2ll].l = curr[md].l;
                        nxt[(curr[md].l + md) / 2ll].r = md;
                    } else {
                        nxt[(curr[md].r + md) / 2ll].arr.push_back(it);
                        nxt[(curr[md].r + md) / 2ll].r = curr[md].r;
                        nxt[(curr[md].r + md) / 2ll].l = md;
                    }
                }
            }
        }
        if(!flag) {break;}
        for(ll i = 0; i <= m; i ++) {
            curr[i] = nxt[i];
        }
    }
    for(ll i = 0; i < q; i ++) {
        cout << ans[i] << endl;
    }
    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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46