Submission #873883

#	Time	Username	Problem	Language	Result	Execution time	Memory
873883		noiaint	Evacuation plan (IZhO18_plan)	C++17	100 / 100	582 ms	103072 KiB

plan

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

class DSU {
    int n;
    vector<int> e;
public:
    DSU(int n) : n (n), e (n, -1) {};

    int find(int x) {
        return e[x] < 0 ? x : e[x] = find(e[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};

struct edge {
    int u, v, c;

    edge(int _u, int _v, int _c = 0) {
        u = _u;
        v = _v;
        c = _c;
    }

    bool operator < (const edge &a) const {
        return c < a.c;
    }
};

int n, m, k;
vector<pair<int, int> > g[N], adj[N];
vector<int> npp;
vector<edge> edges;

// dijkstra
int dis[N];

void dijkstra() {
	for (auto [u, v, c] : edges) {
		g[u].emplace_back(v, c);
		g[v].emplace_back(u, c);
	}

    memset(dis, 0x3f3f3f, sizeof dis);
    typedef pair<int, int> node;
    priority_queue<node, vector<node>, greater<node> > q;
    for (int u : npp) {
    	dis[u] = 0;
    	q.emplace(0, u);
    }

    while (q.size()) {
    	int du, u;
    	tie(du, u) = q.top(); q.pop();
    	if (du > dis[u]) continue;
    	for (auto [v, c] : g[u]) {
    		if (dis[u] + c < dis[v]) {
    			dis[v] = dis[u] + c;
    			q.emplace(dis[v], v);
    		}
    	}
    }
}

void mst() {
    for (auto &[u, v, c] : edges) {
    	c = min(dis[u], dis[v]);
    	// cout << u << ' ' << v << ' ' << c << '\n';
    }

    sort(all(edges));
    reverse(all(edges));

    DSU dsu(n + 5);
    for (auto [u, v, c] : edges) {
    	if (dsu.unite(u, v)) {
    		adj[u].emplace_back(v, c);
    		adj[v].emplace_back(u, c);
    	}
    }
}

// lca
int h[N], l[N];
int par[N][lg + 1], mn[N][lg + 1];

void dfs(int u, int p) {
	for (auto [v, c] : adj[u]) if (v != p) {
		h[v] = h[u] + 1;
		par[v][0] = u;
		mn[v][0] = c;
		dfs(v, u);
	}
}

int max_edge(int u, int v) {
	int res = oo;
	if (h[u] < h[v]) swap(u, v);
	while (h[u] > h[v]) {
		int i = (int) log2(h[u] - h[v]);
		res = min(res, mn[u][i]);
		u = par[u][i];
	}
	if (u == v) return res;
	for (int i = lg; i >= 0; --i) if (par[u][i] != par[v][i]) {
		res = min({res, mn[u][i], mn[v][i]});
		u = par[u][i];
		v = par[v][i];
	}
	res = min({res, mn[u][0], mn[v][0]});
	return res;
}

void PrePathQuery() {
    dfs(1, 0);

    for (int j = 1; j <= lg; ++j) for (int i = 1; i <= n; ++i) {
    	par[i][j] = par[par[i][j - 1]][j - 1];
    	mn[i][j] = min(mn[par[i][j - 1]][j - 1], mn[i][j - 1]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
    	int u, v, c;
    	cin >> u >> v >> c;
    	edges.emplace_back(u, v, c);
    }

    cin >> k;
    for (int i = 1; i <= k; ++i) {
    	int x;
    	cin >> x;
    	npp.push_back(x);
    }

    dijkstra();
    mst();
    PrePathQuery();

    int q;
    cin >> q;
    while (q--) {
    	int u, v;
    	cin >> u >> v;
    	cout << max_edge(u, v) << '\n';
    }

    return 0;
}

/*
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
*/

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