Submission #1131258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131258		harut_13	Evacuation plan (IZhO18_plan)	C++20	100 / 100	507 ms	86680 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD 1000000007


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return ((res) * (res) * (a));
    }
    else {
        return (res) * (res);
    }
}
struct triple {
    int w;
    int u;
    int v;
};
vec par, sizes;
vector < vector<pll>> tree;
int get(int u) {
    if (par[u] == u)return u;
    return par[u] = get(par[u]);
}

void uni(int u, int v) {
    int a = get(u);
    int b = get(v);
    if (sizes[a] < sizes[b])swap(a, b);
    sizes[a] += sizes[b];
    par[b] = a;
}
vector<vecl> up, cnox_mn;
vec tin, tout;
int timer; ll L;
void dfs(int u, int p,ll w) {
    tin[u] = ++timer;
    up[u][0] = p;
    cnox_mn[u][0] = w;
    for (int i = 1; i <= L; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        cnox_mn[u][i] = min(cnox_mn[u][i - 1], cnox_mn[up[u][i - 1]][i - 1]);
    }
    for (auto &x : tree[u]) {
        if (x.first != p) {
            dfs(x.first, u, x.second);
        }
    }
    tout[u] = ++timer;
}
bool cnox(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
ll lca(int u, int v) {
    if (cnox(u, v))return u;
    if (cnox(v, u))return v;
    for (int i = L; i >= 0; i--) {
        if (!cnox(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}
ll lift(int u, int v) {
    ll cur = 1e18;
    for (int i = L; i >= 0; i--) {
        if (cnox(v,up[u][i])) {
            cur = min(cur, cnox_mn[u][i]);
            u = up[u][i];
        }
    }
    return cur;
}
void solve() {
    ll n, m; cin >> n >> m;
    vector<vector<pll>> gp(n);
    vector<pii> koxmer;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        gp[--u].pshb({ --v,w });
        gp[v].pshb({ u,w });
        koxmer.pshb({ u,v });
    }
    int k; cin >> k;
    vec  v(k);
    for (int i = 0; i < k; i++) {
        cin >> v[i];
        v[i]--;
    }
    int q; cin >> q;
    vector<pii> harc(q);
    for (int i = 0; i < q; i++) {
        cin >> harc[i].first;
        cin >> harc[i].second;
        harc[i].first--;
        harc[i].second--;
    }
    vecl d(n, 1e18);
    priority_queue<pll> pq;
    for (int i = 0; i < k; i++) {
        pq.push({ 0,v[i] });
        d[v[i]] = 0;
    }
    cout << endl;
    while (pq.sz) {
        int u = pq.top().second;
        ll w = -1 * pq.top().first;
        pq.pop();
        if (d[u] != w)continue;
        for (auto& x : gp[u]) {
            int to = x.first;
            ll dist = x.second;
            if (dist + w < d[to]) {
                d[to] = dist + w;
                pq.push({ -1 * d[to],to });
            }
        }
    }
    vector<pair<ll,pii>> edge(m);
    for (int i = 0; i < m; i++) {
        int uu = koxmer[i].first;
        int vv = koxmer[i].second;
        ll ww = min(d[uu], d[vv]);
        edge[i].first=ww;
        edge[i].second = {uu,vv};
    }
    tree = vector < vector<pll>>(n);
   sort(edge.rbegin(), edge.rend());
    par = vec(n); for (int i = 0; i < n; i++)par[i] = i;
    sizes = vec(n, 1);
    for (int i = 0; i < m; i++) {
        int uu = edge[i].second.first;
        int vv = edge[i].second.second;
        ll ww = edge[i].first;
        if (get(uu) != get(vv)) {
            uni(uu, vv);
            tree[uu].pshb({ vv,ww });
            tree[vv].pshb({ uu,ww });
        }
    }
     L = ceil(log2(n));
    up =vector<vecl>(n, vecl(L+1));
    cnox_mn = vector<vecl>(n, vecl(L + 1, 1e18));
    tin = tout = vec(n);
    timer = 0;
    dfs(0, 0,1e18);
   //return;
    for (int i = 0; i < q; i++) {
        int u = harc[i].first;
        int v = harc[i].second;
        int cnox = lca(u, v);
        ll x = lift(u, cnox);
        ll y = lift(v, cnox);
        cout << min(x, y) << endl;
   }
}



signed main() {
    FASTIO
        //int t; cin >> t;
    //while (t--)
        solve();


}

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