Submission #153915

#	Time	Username	Problem	Language	Result	Execution time	Memory
153915		andrew	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2296 ms	95928 KiB

plan

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

vector <pll> v[MAXN];
vector <ll> V[MAXN];

ll p[MAXN];

ll get(ll x){
    if(p[x] != x)p[x] = get(p[x]);
    return p[x];
}

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

    ll n, m;
    cin >> n >> m;

    while(m--){
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].p_b({b, c});
        v[b].p_b({a, c});
    }

    set <pll> st;

    vector <ll> dp(n + 1), f(n + 1);

    for(int i = 1; i <= n; i++)dp[i] = 1e18;

    ll k;

    cin >> k;

    map <ll, vector <ll>> mp;

    while(k--){
        ll x;
        cin >> x;
        dp[x] = 0;
        st.insert({0ll, x});
    }

    while(!st.empty()){
        pll xe = *st.begin();
        st.erase(st.begin());
        for(auto i : v[xe.se]){
            ll val = xe.fi + i.se, to = i.fi;
            if(dp[to] > val){
                st.erase({dp[to], to});
                dp[to] = val;
                st.insert({dp[to], to});
            }
        }
    }

    vector <ll> b;

    for(int i = 1; i <= n; i++){
        mp[dp[i]].p_b(i);
    }

    for(auto i : mp)b.p_b(i.fi);

    ll N = b.size();

    ll q;
    cin >> q;

    vector <pll> t(q);

    for(int i = 0; i < q; i++)cin >> t[i].fi >> t[i].se;

    vector <ll> l(q), r(q);

    for(int i = 0; i < q; i++)r[i] = N - 1;

    for(int step = 0; step < 19; step++){
        for(int i = 1; i <= n; i++){
            p[i] = i;
            f[i] = 0;
        }
        for(int i = 0; i < q; i++)if(l[i] < r[i]){
            ll mid = (l[i] + r[i] + 1) >> 1;
            V[mid].p_b(i);
        }

        for(int i = N - 1; i >= 0; i--){
            for(auto k : mp[b[i]]){
                for(auto j : v[k])if(f[j.fi]){
                    if(get(k) != get(j.fi)){
                        p[get(j.fi)] = get(k);
                    }
                }
                f[k] = 1;
            }
            for(auto k : V[i]){
                if(get(t[k].fi) == get(t[k].se))l[k] = i; else r[k] = i - 1;
            }
            V[i].clear();
        }
    }

    for(int i = 0; i < q; i++)cout << b[l[i]] << "\n";

    return 0;
}

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