제출 #69205

#제출 시각아이디문제언어결과실행 시간메모리
69205istleminEvacuation plan (IZhO18_plan)C++14
100 / 100
2855 ms87388 KiB
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = a; i<int(b);++i) #define all(v) v.begin(),v.end() #define sz(v) v.size() #define trav(a,c) for(auto a: c) typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pii; class UnionFind{ public: vi p,r; UnionFind(ll n){ p.resize(n); rep(i,0,n) p[i] = i; r.resize(n,1); } ll find(ll a){ return p[a]==a?a:p[a]=find(p[a]); } void join(ll a,ll b){ a = find(a); b = find(b); if(r[a]>r[b]){ p[b] = a; } else if(r[b]>r[a]){ p[a] = b; } else { p[a] = b; r[b]++; } } }; ll n,k; vector<vector<pii>> ge; vi g; vi dist; void getDists(){ dist.resize(n,-1); set<pii> q; rep(i,0,k) q.emplace(0,g[i]); while(q.size()){ ll v = q.begin()->second; ll d = q.begin()->first; q.erase(q.begin()); if(dist[v]!=-1) continue; dist[v] = d; rep(i,0,ge[v].size()){ q.emplace(d+ge[v][i].second,ge[v][i].first); } } } vector<vector<pii>> e; void makeTree(){ vector<tuple<ll,ll,ll> > edges; rep(i,0,n){ rep(j,0,ge[i].size()){ edges.emplace_back(min(dist[ge[i][j].first],dist[i]),i,ge[i][j].first); } } sort(all(edges)); reverse(all(edges)); UnionFind uf(n); e.resize(n); rep(i,0,edges.size()){ ll a,b,w; tie(w,a,b) = edges[i]; if(uf.find(a)!=uf.find(b)){ uf.join(a,b); e[a].emplace_back(b,w); e[b].emplace_back(a,w); } } } class LCA { public: vi levels; vector<vector<pii> > jump; LCA(){ jump.resize(30,vector<pii>(n)); levels.resize(n); dfs(0,0,0,1e18); rep(i,1,30){ rep(j,0,n){ jump[i][j].first = jump[i-1][jump[i-1][j].first].first; jump[i][j].second = min(jump[i-1][j].second,jump[i-1][jump[i-1][j].first].second); } } } void dfs(ll v,ll last,ll level,ll w){ jump[0][v] = {last,w}; levels[v] = level; rep(i,0,e[v].size()){ if(e[v][i].first==last) continue; dfs(e[v][i].first,v,level+1,e[v][i].second); } } ll getMin(ll a,ll b){ ll mn = 1e18; if(levels[a]<levels[b]) swap(a,b); for(int i = 29; i>=0;--i){ if(levels[jump[i][a].first]>=levels[b]){ mn = min(mn,jump[i][a].second); a = jump[i][a].first; } } assert(levels[a]==levels[b]); if(a==b) return mn; for(int i = 29; i>=0;--i){ if(jump[i][a].first!=jump[i][b].first){ mn = min(mn,jump[i][a].second); a = jump[i][a].first; mn = min(mn,jump[i][b].second); b = jump[i][b].first; } } assert(a!=b); mn = min(mn,jump[0][a].second); a = jump[0][a].first; mn = min(mn,jump[0][b].second); b = jump[0][b].first; assert(a==b); return mn; } }; int main(){ cin.sync_with_stdio(false); ll m; cin>>n>>m; ge.resize(n); rep(i,0,m){ ll a,b,w; cin>>a>>b>>w; --a;--b; ge[a].emplace_back(b,w); ge[b].emplace_back(a,w); } cin>>k; g.resize(k); rep(i,0,k) { cin>>g[i]; --g[i]; } getDists(); //rep(i,0,n) cout<<i+1<<": "<<dist[i]<<endl; makeTree(); /*cout<<"tree"<<endl; rep(i,0,n){ cout<<i+1<<": "; rep(j,0,e[i].size()){ cout<<e[i][j].first+1<<" "; } cout<<endl; }*/ LCA* lca = new LCA(); ll q; cin>>q; rep(i,0,q){ ll a,b; cin>>a>>b; --a; --b; cout<<lca->getMin(a,b)<<endl; } _Exit(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...