Submission #919821

#	Time	Username	Problem	Language	Result	Execution time	Memory
919821		VMaksimoski008	Evacuation plan (IZhO18_plan)	C++14	100 / 100	456 ms	69308 KiB

plan

#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

struct Edge { 
    int a, b;
    ll w;
    bool operator<(Edge &e) const { return w < e.w; }
};

struct DSU {
    int n, comp;
    vector<int> par, size;

    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }

    bool uni(int u, int v) {
        u = get(u), v = get(v);

        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);

        size[u] += size[v];
        par[v] = u;
        comp--;

        return true;
    }

    int getComp() { return comp; }
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
};

vector<vector<pll> > G;
int depth[maxn+1], up[maxn+1][LOG];
ll mn[maxn+1][LOG];

void dfs(int u, int p) {
    for(int i=1; i<LOG; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
        mn[u][i] = min(mn[u][i-1], mn[up[u][i-1]][i-1]);
    }

    for(auto &[v, w] : G[u]) {
        if(v == p) continue;
        up[v][0] = u;
        mn[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

ll get_lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);

    ll ans = 1e18;
    int d = depth[a] - depth[b];
    for(int j=LOG-1; j>=0; j--) {
        if(d & (1 << j)) {
            ans = min(ans, mn[a][j]);
            a = up[a][j];
        }
    }

    if(a == b) return ans;

    for(int j=LOG-1; j>=0; j--) {
        if(up[a][j] != up[b][j]) {
            ans = min(ans, mn[a][j]);
            ans = min(ans, mn[b][j]);
            a = up[a][j];
            b = up[b][j];
        }
    }

    return min({ ans, mn[a][0], mn[b][0] });
}

int32_t main() {
    setIO();

    int n, m;
    cin >> n >> m;
    vector<vector<pii> > graph(n+1);
    vector<Edge> edges(m);
    G.resize(n+1);

    for(Edge &e : edges) {
        cin >> e.a >> e.b >> e.w;
        graph[e.a].push_back({ e.b, e.w });
        graph[e.b].push_back({ e.a, e.w });
    }
    
    int spec;
    cin >> spec;

    priority_queue<pll, vector<pll>, greater<pll> > pq;
    vector<bool> vis(n+1);
    vector<ll> dist(n+1, 1e18);

    while(spec--) {
        int x;
        cin >> x;
        dist[x] = 0;
        pq.push({ 0, x });
    }

    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if(vis[u]) continue;
        vis[u] = 1;

        for(auto &[v, w] : graph[u]) {
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({ dist[v], v });
            }
        }
    }

    for(Edge &e : edges) e.w = min(dist[e.a], dist[e.b]);
    sort(rall(edges));

    DSU dsu;
    dsu.config(n);

    for(Edge &e : edges) {
        if(dsu.uni(e.a, e.b)) {
            G[e.a].push_back({ e.b, e.w });
            G[e.b].push_back({ e.a, e.w });
        }
    }

    dfs(1, 0);

    int q;
    cin >> q;

    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << get_lca(a, b) << '\n';
    }

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dfs(int, int)':
plan.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto &[v, w] : G[u]) {
      |               ^
plan.cpp: In function 'int32_t main()':
plan.cpp:152:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |         for(auto &[v, w] : graph[u]) {
      |                   ^

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