제출 #1093972

#제출 시각아이디문제언어결과실행 시간메모리
1093972ToTenLinhEvacuation plan (IZhO18_plan)C++17
100 / 100
522 ms63908 KiB
#include <bits/stdc++.h> #define fo(i,m,n) for(int i=m;i<=n;i++) #define fod(i,n,m) for(int i=n;i>=m;i--) #define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k) #define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k) #define fol(i,m,n) for(long long i=m;i<=n;i++) #define fodl(i,n,m) for(long long i=n;i>=m;i--) #define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k) #define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k) #define lb lower_bound #define ub upper_bound #define pii pair <int,int> #define vii vector<pii> #define fi first #define se second #define si size() #define pb push_back #define ppb pop_back() #define fr front() #define et empty() #define bg begin() #define ub upper_bound #define lb lower_bound #define ed end() #define el endl #define EL cout << '\n'; using namespace std; using ll = long long ; #define int ll const int mod = 1e9 + 7; const int N = 1e5 + 69; const int M = 1e3 + 5; template<class T> constexpr T inf = ::numeric_limits<T>::max() / 32 * 15 + 208; int n, m, k, q, city[N] ; ll dist[N] ; ll a[N] ; vector<pair<ll,int>> g[N]; vector<int> adj[N] ; void djickstra() { for (int i = 1 ; i <= n ; i++) { dist[i] = inf<ll> ; } set<pair<ll,int>> st; for (int i = 0 ; i < k ; i++) { st.insert({0, city[i]}) ; dist[city[i]] = 0 ; } while (st.size()) { auto [val, v] = *st.begin() ; st.erase(st.begin()) ; for (auto [w, to] : g[v]) { if (dist[to] > dist[v] + w) { st.erase({dist[to], to}) ; dist[to] = dist[v] + w ; st.insert({dist[to], to}) ; } } } } struct DSU { vector<int> parent, sz ; DSU(int n) { parent.resize(n) ; iota(begin(parent), end(parent), 0) ; sz.assign(n, 1) ; } int find(int i) { if (i == parent[i]) { return i ; } else { return parent[i] = find(parent[i]) ; } } bool unite(int u, int v) { u = find(u), v = find(v) ; if (u == v) return false ; if (sz[v] == sz[u]) sz[v]++ ; if (sz[v] < sz[u]) swap(u, v) ; parent[u] = v ; return true ; } bool same(int u, int v) { return (find(u) == find(v)) ; } }; int chain[N], sz[N] ; int tin[N], timer, t[N * 4], c[N], pr[N], depth[N] ; void dfs(int v, int p) { pr[v] = p ; sz[v] = 1 ; for (auto to : adj[v]) { if (to != p) { depth[to] = depth[v] + 1 ; dfs(to, v) ; sz[v] += sz[to] ; } } } void hld(int v, int p, int head) { tin[v] = ++timer ; chain[v] = head ; int cur = 0 ; for (auto to : adj[v]) { if (to != p && sz[to] > sz[cur]) cur = to ; } if (cur) { hld(cur, v, head) ; } for (auto to : adj[v]) { if (to == p || to == cur) { continue ; } hld(to, v, to) ; } } void upd(int i, int x, int v, int tl, int tr) { if (tl == tr) { t[v] = x ; } else { int tm = (tl + tr) / 2; if (i <= tm) { upd(i, x, v * 2, tl, tm) ; } else { upd(i, x, v * 2 + 1, tm + 1, tr) ; } t[v] = min(t[v * 2], t[v * 2 + 1]) ; } } int get(int l, int r, int v, int tl, int tr) { if (l > r) swap(l, r) ; if (l > tr || r < tl) return inf<ll> ; if (l <= tl && tr <= r) return t[v] ; int tm = (tl + tr) / 2; return min(get(l,r,v*2,tl,tm), get(l,r,v*2+1,tm+1,tr)) ; } int query(int u, int v) { int ans = inf<ll> ; while (chain[u] != chain[v]) { if (depth[chain[u]] < depth[chain[v]]) swap(u, v) ; int boss = chain[u] ; if (u == boss) { ans = min(ans, a[u]) ; u = pr[u] ; } else { ans = min(ans, get(tin[u], tin[boss], 1, 1, n)) ; u = pr[boss] ; } } int l = tin[u], r = tin[v] ; ans = min(ans, get(l,r,1,1,n)) ; return ans ; } signed main() { cin.tie(0)->sync_with_stdio(false) ; cin >> n >> m; vector<tuple<ll,ll,ll>> edge(m) ; for (int i = 0 ; i < m ; i++) { ll u, v, w ; cin >> u >> v >> w ; g[u].push_back({w, v}) ; g[v].push_back({w, u}) ; edge[i] = {0, u, v} ; } cin >> k; for (int i = 0 ; i < k ; i++) { cin >> city[i] ; } djickstra() ; for (int i = 0 ; i < m ; i++) { auto& [val, u, v] = edge[i] ; val = min(dist[u], dist[v]) ; } sort(edge.rbegin(), edge.rend()) ; int ptr = -1 ; DSU d(n + 1) ; for (auto [val, u, v] : edge) { if (d.unite(u, v)) { adj[u].push_back(v) ; adj[v].push_back(u); } } dfs(1, 0) ; hld(1, 0, 1) ; for (int i = 1 ; i <=n ; i++) { a[i] = dist[i] ; } for (int i = 1 ; i <= n ; i++) { upd(tin[i], a[i], 1, 1, n) ; } cin >> q; while (q--) { int u, v; cin >> u >> v; cout << query(u, v) << "\n" ; } return 0 ; }

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:222:9: warning: unused variable 'ptr' [-Wunused-variable]
  222 |     int ptr = -1 ;
      |         ^~~
#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...