제출 #850957

#제출 시각아이디문제언어결과실행 시간메모리
850957wakandaaaEvacuation plan (IZhO18_plan)C++17
0 / 100
199 ms76112 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...