Submission #343295

#	Time	Username	Problem	Language	Result	Execution time	Memory
343295		Traduttore	Evacuation plan (IZhO18_plan)	C++17	35 / 100	732 ms	56428 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 qb;
    cin>>qb;
    int yac = 0;
    vector <int> distan(n, -1);
    while (qb--)
    {
        int x,y;
        cin>>x>>y;
        --x;
        --y;
        if (n > 5e3) {
            ans = min(dist[x],dist[y]);
            output();
            continue;
        }
       int left = 0;
        int right = dists.size() - 1;
        ans = 0;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int lvl = dists[mid].F;
            if (dist[x] < lvl || dist[y] < lvl) {
                ++yac;
                right = mid - 1;
                continue;
            }
            queue <int> q;
            q.push(x);
            distan[x] = yac;
            while (!q.empty())
            {
                int v = q.front();
                q.pop();
                if (distan[y] == yac) break;
                if (dist[v] < lvl) continue;
                if (v == y) continue;
                for (auto to:gr[v]) {
                    if (dist[to.F] < lvl) continue;
                    if (distan[to.F] != yac) {
                        distan[to.F] = yac;
                        q.push(to.F);
                    }
                }
            }
            if (distan[y] == yac) {
                ans = lvl;
                left = mid + 1;
            }
            else right = mid - 1;
            ++yac;
        }
        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: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46