Submission #343268

#	Time	Username	Problem	Language	Result	Execution time	Memory
343268		Traduttore	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4045 ms	55856 KiB

plan

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define F first
#define S second
#define ull unsigned long long
#define ld long double
#define endl '\n'
#define ll long long
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int32_t , int32_t >
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pll pair <ll,ll>


using namespace std;
using namespace __gnu_pbds;

const int32_t N = 2e5 + 23;
const int rx[] = {-1, +1, 0, 0};
const int ry[] = {0, 0, -1, +1};
typedef tree <int,null_type,less <int>,rb_tree_tag,tree_order_statistics_node_update> orduk;
typedef tree <pair <int,pll>,null_type,less <pair <int,pll> >,rb_tree_tag,tree_order_statistics_node_update> orduk2;
mt19937_64 gen(time(NULL));
ll n,m;
vector <pll> gr[(int)(1e6)];
vector <ll> a;
void init() {
    cin>>n>>m;
    for (int i = 0;i < m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        --x;
        --y;
        gr[x].pb({y,z});
        gr[y].pb({x,z});
    }
}
ll ans = 0;
void output() {
cout<<ans<<'\n';
}
void solve() {
    vector <ll> dist(n, 2e18);
    ll v;
    cin>>v;
    for (int i = 0;i < v;i++)
    {
        int x;
        cin>>x;
        --x;
        dist[x] = 0;
        queue <ll> q;
        q.push(x);
        while (!q.empty()) {
            ll v = q.front();
            q.pop();
            for (auto to:gr[v])
            if (to.S + dist[v] < dist[to.F]) {
                dist[to.F] = to.S + dist[v];
                q.push(to.F);
            }
        }
    }
    vector <pll> dists(n);
    for (int i = 0;i < n;i++)
    {
        dists[i].F = dist[i];
        dists[i].S = i;
    }
    sort(dists.begin(),dists.end());
    vector <int> pos(n);
    for (int i = 0;i < n;i++)
        pos[dists[i].S] = i;
    int q;
    cin>>q;
    while (q--)
    {
        int x,y;
        cin>>x>>y;
        --x;
        --y;
        int left = 0;
        int right = n * 1000;
        ans = 0;
        while (left <= right) {
            int mid = (left + right) >> 1;
            pll cur = {mid, -1};
            int lvl = lower_bound(dists.begin(),dists.end(),cur)-dists.begin();
            queue <int> q;
            q.push(x);
            vector <int> dists(n, 2e9);
            while (!q.empty())
            {
                int v = q.front();
                q.pop();
                if (dists[y] == -1) break;
                if (pos[v] < lvl) continue;
                if (v == y) continue;
                for (auto to:gr[v]) {
                    if (pos[to.F] < lvl) continue;
                    if (dists[to.F] == 2e9) {
                        dists[to.F] = -1;
                        q.push(to.F);
                    }
                }
            }
            if (dists[y] == -1) {
                ans = mid;
                left = mid + 1;
            }
            else right = mid - 1;
        }
        output();
    }
}
int32_t main() {
    IOS;
    srand(time(0));
    int32_t m;
    m = 10;
    m-=9;
    while (m--)
    {
        init();
        solve();
    }
    return 0;
}

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