Submission #448334

#TimeUsernameProblemLanguageResultExecution timeMemory
448334ak2006Evacuation plan (IZhO18_plan)C++14
0 / 100
699 ms99696 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 ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } struct DSU { int n; vi p; DSU(int _n) { n = _n; p.assign(n + 1,0); for (int i = 1;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 (b != a) p[b] = a; } }; int n = 1e5 + 5,TIMER = 1; vvvl adj(n),graph(n); vi in(n),out(n); vvi anc(n,vi(21)); vvl dp(n,vl(21,inf)); vl dist(n,inf); vvi edges; 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]; if (v == p)continue; dfs(v,u,val[1]); } 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 (in[u] > in[v])swap(u,v); if (is_ancestor(u,v))return u; for (int i = 20;i>=0;i--){ if (!is_ancestor(u,anc[v][i]))v = anc[v][i]; } return anc[v][0]; } ll minOnPath(int u,int lca) { ll ret = inf; for (int i = 20;i>=0;i--){ if (!is_ancestor(lca,anc[u][i])){ ret = min(ret,dp[u][i]); u = anc[u][i]; } } return min(ret,dp[u][0]); } int main() { setIO(); int n,m,q,k; cin>>n>>m; priority_queue<pair<ll,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; qe.pop(); for (auto val:adj[u]){ int v = val[0]; ll w = val[1]; if (dist[v] > dist[u] + w){ dist[v] = dist[u] + w; qe.push({-dist[v],v}); } } } vvl tree; for (auto e:edges){ int u = e[0],v = e[1]; ll 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]; ll 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; int lca = LCA(u,v); cout<<min(minOnPath(u,lca),minOnPath(v,lca))<<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...