Submission #536139

#	Time	Username	Problem	Language	Result	Execution time	Memory
536139		ddy888	Evacuation plan (IZhO18_plan)	C++17	100 / 100	608 ms	114140 KiB

plan

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

struct edge {
    int u, v, c;
};

const int INF = 1e14;
int N, M, K, Q;
int toxic[100010], dist[100010];
vector<pi> adj[100010], tree[100010];
vector<edge> edges, proc;
priority_queue<pi, vector<pi>, greater<pi> > pq;

int par[100010];
int root(int x) { return (par[x]==x)? x:par[x]=root(par[x]); }
bool same(int a, int b) { return root(a) == root(b); }
void merge(int a, int b) {
    par[root(a)] = root(b);
}

void dijkstra() {
    while (pq.size()) {
        auto [d, x] = pq.top(); pq.pop();
        if (dist[x] != d) continue;
        for (auto i: adj[x]) {
            if (dist[i.fi] == -1 || dist[i.fi] > i.si + d) {
                dist[i.fi] = i.si + d;
                pq.push({dist[i.fi], i.fi});
            }
        }
    }
}

int twok[100010][20], depth[100010], mn[100010][20];

void dfs(int x, int par, int d, int pw) {
    twok[x][0] = par;
    depth[x] = d;
    for (int i = 1; i <= 17; i++) {
        if (twok[x][i-1] == -1) break;
        twok[x][i] = twok[twok[x][i-1]][i-1];
    }
    mn[x][0] = pw;
    for (int i = 1; i <= 17; i++) {
        if (twok[x][i-1] == -1) break;
        mn[x][i] = min(mn[x][i - 1], mn[twok[x][i-1]][i-1]);
    }
    for (auto it: tree[x]) {
        if (it.first != par) dfs(it.first,x,d+1,it.second);
    }
}

signed main() {
    fast;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int u, v, c; cin >> u >> v >> c;
        edges.pb({u, v, c});
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
    cin >> K;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < K; ++i) {
        int x; cin >> x;
        toxic[x] = 1;
        dist[x] = 0;
        pq.push({0, x});
    }
    dijkstra();

    for (int i = 1; i <= N; ++i) par[i] = i;
    for (auto i: edges) proc.pb({i.u, i.v, min(dist[i.u], dist[i.v])});
    sort(proc.begin(), proc.end(), [](edge a, edge b){return a.c > b.c;});
    for (auto i: proc) {
        if (same(i.u, i.v)) continue;
        tree[i.u].pb({i.v, i.c});
        tree[i.v].pb({i.u, i.c});
        merge(i.u, i.v);
    }

    memset(twok, -1, sizeof twok);
    dfs(1, -1, 0, 0);

    cin >> Q;
    while (Q--) {
        int a, b; cin >> a >> b; int ans = INF;
        if (depth[a] > depth[b]) swap(a,b);
        int dd = depth[b] - depth[a];
        for (int i = 0; i <= 17; i++) {
            if (dd & (1<<i)) {
                ans = min(ans,mn[b][i]);
                b = twok[b][i];
            }
        }
        if (a==b) {
            cout << ans << '\n';
            continue;
        }
        for (int i = 17; i >= 0; i--) {
            if (twok[a][i] != twok[b][i]) {
                ans = min(ans, mn[a][i]);
                ans = min(ans, mn[b][i]);
                a = twok[a][i];
                b = twok[b][i];
            }
        }
        ans = min(ans, mn[a][0]);
        ans = min(ans, mn[b][0]);
        cout << ans << '\n';
    }
    return 0;
}

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