제출 #47721

#제출 시각아이디문제언어결과실행 시간메모리
47721dqhungdlEvacuation plan (IZhO18_plan)C++17
54 / 100
4042 ms45496 KiB
#include <bits/stdc++.h> using namespace std; const int MAX=17; typedef pair<int,int> ii; int n,m,k,T,d[100005],R[100005],h[100005],P[100005][20],mind[100005][20]; vector<ii> Edge,g[100005],gg[100005]; set<ii> s; bool cmp(ii x1,ii x2) { return min(d[x1.first],d[x1.second])>min(d[x2.first],d[x2.second]); } int Find(int u) { if(u==R[u]) return u; return R[u]=Find(R[u]); } void Union(int u,int v) { if(u>v) R[u]=v; else R[v]=u; } void Enter() { cin>>n>>m; int u,v,w; while(m--) { cin>>u>>v>>w; Edge.push_back(ii(u,v)); g[u].push_back(ii(v,w)); g[v].push_back(ii(u,w)); } for(int i=1;i<=n;i++) { d[i]=1e9; R[i]=i; } cin>>k; while(k--) { cin>>u; s.insert(ii(0,u)); d[u]=0; } } void BFS() { while(s.size()>0) { int u=(*s.begin()).second; s.erase(s.begin()); for(int i=0;i<g[u].size();i++) { int v=g[u][i].first; int w=g[u][i].second; if(d[v]>d[u]+w) { if(d[v]!=1e9) s.erase(s.find(ii(d[v],v))); d[v]=d[u]+w; s.insert(ii(d[v],v)); } } } } void DFS(int u,int high) { h[u]=high; for(int i=0;i<gg[u].size();i++) { int v=gg[u][i].first; int w=gg[u][i].second; if(h[v]==0) { P[v][0]=u; mind[v][0]=w; DFS(v,high+1); } } } int LCA(int u,int v) { int rs=1e9; for(int k=MAX;k>=0;k--) if(h[P[u][k]]>=h[v]) { rs=min(rs,mind[u][k]); u=P[u][k]; } else if(h[P[v][k]]>=h[u]) { rs=min(rs,mind[v][k]); v=P[v][k]; } for(int k=10;k>=0;k--) if(P[u][k]!=P[v][k]) { rs=min(rs,mind[u][k]); rs=min(rs,mind[v][k]); u=P[u][k]; v=P[v][k]; } while(u!=v) { rs=min(rs,mind[u][0]); rs=min(rs,mind[v][0]); u=P[u][0]; v=P[v][0]; } return rs; } void InitTree() { sort(Edge.begin(),Edge.end(),cmp); for(int i=0;i<Edge.size();i++) { int u=Edge[i].first; int v=Edge[i].second; int w=min(d[u],d[v]); if(Find(u)!=Find(v)) { Union(Find(u),Find(v)); gg[u].push_back(ii(v,w)); gg[v].push_back(ii(u,w)); } } DFS(1,1); for(int k=1;k<=MAX;k++) for(int i=1;i<=n;i++) { P[i][k]=P[P[i][k-1]][k-1]; mind[i][k]=min(mind[i][k-1],mind[P[i][k-1]][k-1]); } } void Query() { cin>>T; int u,v; while(T--) { cin>>u>>v; cout<<LCA(u,v)<<"\n"; } } int main() { ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); //freopen("TEST.OUT","w",stdout); Enter(); BFS(); InitTree(); Query(); }

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

plan.cpp: In function 'void BFS()':
plan.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++)
               ~^~~~~~~~~~~~
plan.cpp: In function 'void DFS(int, int)':
plan.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<gg[u].size();i++)
              ~^~~~~~~~~~~~~
plan.cpp: In function 'void InitTree()':
plan.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Edge.size();i++)
              ~^~~~~~~~~~~~
#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...