Submission #388601

#	Time	Username	Problem	Language	Result	Execution time	Memory
388601		SavicS	Evacuation plan (IZhO18_plan)	C++14	0 / 100	305 ms	16116 KiB

plan

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

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

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

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m, k, q;

vector<pii> g[maxn];

pii upit[maxn];
bool mark[maxn];

int dist[maxn];
void dij() {
    ff(i,1,n)dist[i] = inf;

    priority_queue<pii,vector<pii>, greater<pii>> pq;
    ff(i,1,n) {
        if(mark[i] == 1)pq.push({dist[i] = 0, i});
    }

    while(!pq.empty()) {
        pii v = pq.top();
        pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(auto c : g[v.se]) {
            int u = c.fi;
            int w = c.se;
            if(dist[u] > v.fi + w) {
                dist[u] = v.fi + w;
                pq.push({dist[u], u});
            }
        }
    }

}

int par[maxn], sz[maxn];
int findpar(int x) {
    return (x == par[x] ? x : par[x] = findpar(par[x]));
}
void unite(int x, int y) {
    x = findpar(x);
    y = findpar(y);
    if(x == y)return;
    if(sz[x] < sz[y])swap(x, y);
    par[y] = x;
    sz[x] += sz[y];
}


bool dobar[maxn];

int res[maxn];
void divi(int l, int r, vector<int> eve) {
    if(eve.empty() || l > r)return;

    int mid = (l + r) / 2;

    vector<int> svi;
    ff(i,1,n) {
        if(dist[i] >= mid) {
            dobar[i] = 1;
            par[i] = i;
            sz[i] = 1;
            svi.pb(i);
        }
    }

    ff(i,0,sz(svi) - 1) {
        int A = svi[i];
        for(auto c : g[A]) {
            if(dobar[c.fi] == 1)unite(A, c.fi);
        }
    }

    vector<int> ok, not_ok;

    for(auto c : eve) {
        int S = upit[c].fi;
        int T = upit[c].se;
        if(findpar(S) == findpar(T) && dobar[S] == 1 && dobar[T] == 1) {
            res[c] = mid;
            ok.pb(c);
        } else not_ok.pb(c);
    }

    ff(i,1,n) {
        if(dist[i] >= mid)dobar[i] = 0;
    }

    divi(l, mid - 1, not_ok);
    divi(mid + 1, r, ok);

}

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> m;
    ff(i,1,m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    cin >> k;
    ff(i,1,k) {
        int X;
        cin >> X;
        mark[X] = 1;
    }

    cin >> q;
    ff(i,1,q) {
        int S, T;
        cin >> S >> T;
        upit[i] = {S, T};
    }

    dij();

    vector<int> kwe;
    ff(i,1,q)kwe.pb(i);

    divi(1, 20, kwe);

    ff(i,1,q)cout << res[i] << '\n';

    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

// probati bojenje sahovski ili slicno

**/

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