제출 #448347

#제출 시각아이디문제언어결과실행 시간메모리
448347ak2006Evacuation plan (IZhO18_plan)C++14
0 / 100
580 ms91676 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; const int inf = 1e9; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } int RET = inf; struct DSU { vi p,sz; int n; DSU(int _n) { n = _n; p.assign(n + 1,-1); sz.assign(n + 1,1); for (int i = 0;i<=n;i++)p[i] = i; } int Find(int a) { if (p[a] == a)return a; return p[a] = Find(p[a]); } void Unite(int a,int b) { a = Find(a),b = Find(b); if (a == b)return; if (sz[a] < sz[b])swap(a,b); p[b] = a; sz[b] += sz[a]; } }; int n = 1e5 + 5,TIMER = 1; vvvi adj(n),graph(n); vi in(n),out(n),dist(n,inf); vvi anc(n,vi(21)),dp(n,vi(21,inf)),edges,tree; void dfs(int u,int p,ll w) { in[u] = TIMER++; anc[u][0] = p; dp[u][0] = w; for (int i = 1;i<=20;i++){ anc[u][i] = anc[anc[u][i - 1]][i - 1]; dp[u][i] = min(dp[u][i - 1],dp[anc[u][i - 1]][i - 1]); } for (auto val:graph[u]){ int v = val[0],wt = val[1]; if (v == p)continue; dfs(v,u,wt); } out[u] = TIMER++; } bool is_ancestor(int u,int v) { return in[u] <= in[v] && out[u] >= out[v]; } int LCA(int u,int v) { if (is_ancestor(u,v))return u; for (int i = 20;i>=0;i--) if (!is_ancestor(anc[u][i],v)){ cout<<u<<" "<<i<<" "<<dp[u][i]<<endl; RET = min(RET,dp[u][i]); u = anc[u][i]; } RET = min(RET,dp[u][0]); return anc[u][0]; } void query(int u,int v) { if (u == v)return; for (int i = 20;i>=0;i--){ if (!is_ancestor(anc[u][i],v)){ RET = min(RET,dp[u][i]),u = anc[u][i]; } } RET = min(RET,dp[u][0]); } int main() { setIO(); int n,m,q,k; cin>>n>>m; priority_queue<pair<int,int>>qe; while (m--){ int u,v,w; cin>>u>>v>>w; adj[u].pb({v,w}),adj[v].pb({u,w}); edges.pb({u,v}); } cin>>k; while (k--){ int u; cin>>u; dist[u] = 0; qe.push({0,u}); } while (!qe.empty()){ int u = qe.top().second; int d = -qe.top().first; qe.pop(); if (dist[u] != d)continue; for (auto val:adj[u]){ int v = val[0]; int w = val[1]; if (dist[v] > dist[u] + w){ dist[v] = dist[u] + w; qe.push({-dist[v],v}); } } } for (auto e:edges){ int u = e[0],v = e[1],w = min(dist[u],dist[v]); tree.pb({w,u,v}); } sort(tree.rbegin(),tree.rend()); DSU val(n); for (auto it:tree){ int u = it[1],v = it[2],w = it[0]; if (val.Find(u) == val.Find(v))continue; val.Unite(u,v); graph[u].pb({v,w}); graph[v].pb({u,w}); } dfs(1,1,inf); cin>>q; while (q--){ int u,v; cin>>u>>v; if (in[u] > in[v])swap(u,v); RET = inf; int l = LCA(u,v); query(v,l); cout<<RET<<endl; } return 0; }
#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...