Submission #496328

#	Time	Username	Problem	Language	Result	Execution time	Memory
496328		armashka	Evacuation plan (IZhO18_plan)	C++17	0 / 100	291 ms	92176 KiB

plan

#include <bits/stdc++.h>
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }
 
struct queries {
    int u, v, w;
};
 
int n, m, k, pr[N * 20], ls[N * 20], rs[N * 20], root[N], d[N], cnt;
vector <pair<int, int>> g[N];
vector <int> s[N];
queries que[N];
 
void build(int &v, int tl = 1, int tr = n) {
    if (!v) v = ++ cnt;
    if (tl == tr) {
        pr[v] = tl;
        return;
    }
    int tm = (tl + tr) / 2;
    build(ls[v], tl, tm);
    build(rs[v], tm + 1, tr);
}
 
void upd(int pos, int val, int &v, int lv, int tl = 1, int tr = n) {
    if (!v) v = ++ cnt;
    if (tl == tr) {
        pr[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
        rs[v] = rs[lv];
        upd(pos, val, ls[v], ls[lv], tl, tm);
    } else {
        ls[v] = ls[lv];
        upd(pos, val, rs[v], rs[lv], tm + 1, tr);
    }
}
 
int get(int pos, int v, int tl = 1, int tr = n) {
    if (tl == tr) {
        return pr[v];
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) return get(pos, ls[v], tl, tm);
    else return get(pos, rs[v], tm + 1, tr);
}
 
const void solve(/*Armashka*/) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        cin >> que[i].u >> que[i].v >> que[i].w;
        g[que[i].u].pb({que[i].v, que[i].w});
        g[que[i].v].pb({que[i].u, que[i].w});
    }
    for (int i = 1; i <= n; ++ i) d[i] = inf;
    cin >> k;
    queue <int> q;
    for (int i = 1; i <= k; ++ i) {
        int x; cin >> x;
        d[x] = 0; q.push(x);
    }
    while (q.sz) {
        int v = q.front();
        q.pop();
        for (auto [to, w] : g[v]) {
            if (d[to] > d[v] + w) {
                d[to] = d[v] + w;
                q.push(to);
            }
        }
    }
    vector <pair<int, pair<int,int>>> dis;
    for (int i = 1; i <= m; ++ i) {
        dis.pb({min(d[que[i].u], d[que[i].v]), {que[i].u, que[i].v}});
    }
    for (int i = 1; i <= n; ++ i) s[i].pb(i);
    sort(all(dis));
    reverse(all(dis));
    build(root[0]);
    for (int i = 1; i <= m; ++ i) {
        int a = dis[i - 1].sd.ft, b = dis[i - 1].sd.sd;
        a = get(a, root[i - 1]);
        b = get(b, root[i - 1]);
        if (s[a].sz > s[b].sz) swap(a, b);
        if (a == b) { root[i] = root[i - 1]; continue; }
        for (auto x : s[a]) {
            s[b].pb(x);
            upd(x, b, root[i], root[i - 1]);
        }
    }
    int qq; cin >> qq;
    for (int i = 1; i <= qq; ++ i) {
		int a, b;
    	cin >> a >> b;
		ll l = 1, r = m, ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			if (get(a, root[mid]) == get(b, root[mid])) r = mid - 1, ans = mid;
			else l = mid + 1;
		}
		cout << dis[ans - 1].ft << "\n";
	}
}
 
/*
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
*/
 
signed main() {
    fast;
    int tt = 1;
    // cin >> tt;
    while (tt --)
        solve();
}

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