Submission #1289782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289782		i_love_kim_ji_won	Evacuation plan (IZhO18_plan)	C++20	100 / 100	313 ms	62336 KiB

plan

// I ♡ 김지원
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;

using ll = long long;

void justDoIt();

int main() {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    justDoIt();
    return 0;
}


const int N = 5e5 + 5;

struct Edges {
    int v;
    ll w;
};
struct twoheadedges {
    int u, v;
    ll w;
};

bool Cmpedge(twoheadedges a, twoheadedges b) {
    return a.w > b.w;
}

vector<Edges> g[N];
int u[N], v[N], w[N];
ll dist[N];

struct Node {
    int u;
    ll dist;
};

struct Cmp {
    bool operator() (Node a, Node b) {
        return a.dist > b.dist;
    }
};

priority_queue<Node, vector<Node>, Cmp> q;

void Dijkstra() {
    while (!q.empty()) {
        Node t = q.top(); q.pop();
        for (auto e : g[t.u]) {
            if (dist[e.v] > dist[t.u] + e.w) {
                dist[e.v] = dist[t.u] + e.w;
                q.push({e.v, dist[e.v]});
            }
        }
    }
}

int par[N];

int find_set(int u) {
    return (u == par[u] ? u : par[u] = find_set(par[u]));
}

bool union_set(int u, int v) {
    u = find_set(u), v = find_set(v);
    if (u != v) {
        par[v] = u;
        return 0;
    }
    return 1;
}

int up[N][20];
int h[N];
int mn[N][20];

void dfs(int u) {
    for (auto id : g[u]) {
        if (id.v == up[u][0]) {
            continue;
        }
        h[id.v] = h[u] + 1;
        up[id.v][0] = u;
        mn[id.v][0] = id.w;
        for (int k = 1; k < 20; k++) {
            up[id.v][k] = up[up[id.v][k - 1]][k - 1];
            mn[id.v][k] = min(mn[id.v][k - 1], mn[up[id.v][k - 1]][k - 1]);
        }
        dfs(id.v);
    }
}

int lca(int u, int v) {
    if (h[u] != h[v]) {
        if (h[u] < h[v]) {swap(u, v);}
        int k = h[u] - h[v];
        for (int i = 0; i < 19; i++) {
            if (k >> i & 1) {
                u = up[u][i];
            }
        }
    }
    if (u == v) {return u;}
    int k = __lg(h[u]);
    for (int i = k; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i], v = up[v][i];
        }
    }
    return up[u][0];
}

int get(int u, int p) {
    int res = 1e9;
    int k = h[u] - h[p];
    for (int i = 19; i >= 0; i--) {
        if (k >> i & 1) {
            res = min(res, mn[u][i]);
            u = up[u][i];
        }
    }
    return res;
}

int query_path(int u, int v) {
    int l = lca(u, v);
    return min(get(u, l), get(v, l));
}


void test() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        dist[i] = 1e18;
        par[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        g[u[i]].push_back({v[i], w[i]});
        g[v[i]].push_back({u[i], w[i]});
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        dist[x] = 0;
        q.push({x, 0});
    }
    Dijkstra();
    vector<twoheadedges> e;
    for (int i = 1; i <= m; i++) {
        e.push_back({u[i], v[i], min(dist[u[i]], dist[v[i]])});
    }
    sort(e.begin(), e.end(), Cmpedge);
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }
    int root = 0;
    for (auto id : e) {
        if (!union_set(id.u, id.v)) {
            g[id.u].push_back({id.v, id.w});
            g[id.v].push_back({id.u, id.w});
            root = id.u;
        }
    }
    dfs(root);
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << query_path(x, y) << '\n';
    }
}

void justDoIt() {
    int t = 1;
    // cin >> t;
    for (int tests = 1; tests <= t; tests++) {
        test();
    }
}

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