제출 #1093999

#제출 시각아이디문제언어결과실행 시간메모리
1093999doducanhEvacuation plan (IZhO18_plan)C++14
100 / 100
590 ms59416 KiB
///breaker ///every second counts #include<bits/stdc++.h> using namespace std; struct duongdi{ int u,w; bool operator<(const duongdi&d2)const{ return w > d2.w; } }; struct edge { int u,v,w; bool operator<(const edge&b)const{ return w>b.w; } }; const int maxn=1e5+7; edge e[5*maxn]; vector<pair<int, int>>adj1[maxn],adj2[maxn]; int d[maxn],r[maxn],p[maxn][25], dp[maxn][25]; int h[maxn]; priority_queue<duongdi>q; int sz[maxn]; int Find(int u){ return ((u==r[u])?u:r[u]=Find(r[u])); } void dfs(int u, int pa){ for(auto[v,w]:adj2[u]){ if(v == pa) continue; p[v][0] = u; dp[v][0] = w; h[v]=h[u]+1; dfs(v, u); } } int lca(int u, int v){ if(h[u]<h[v])swap(u, v); int diff=h[u]-h[v]; int mn=1e9+7; for(int i=20;i>=0;i--)if((diff>>i)&1){ mn=min(mn,dp[u][i]); u=p[u][i]; } if(u == v) return mn; for(int i = 20; i>=0; --i){ if(p[u][i]!=p[v][i]){ mn=min({mn, dp[u][i], dp[v][i]}); u=p[u][i]; v=p[v][i]; } } return min({mn,dp[u][0],dp[v][0]}); } int main(){ // freopen("walk.inp","r",stdin); // freopen("walk.out","w",stdout); // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m,k,t; cin>>n>>m; for(int i=0;i<=20;i++){ for(int j=1;j<=n;j++){ dp[j][i]=1e9+7; } } for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; adj1[u].push_back({v, w}); adj1[v].push_back({u, w}); e[i].u=u; e[i].v=v; } for(int i = 1; i<=n; ++i)d[i] = 1e9; for(int i = 1; i<=n; ++i){ r[i] = i; sz[i]=1; } cin>>k; for(int i = 1; i<=k; ++i){ int u; cin>>u; d[u]=0; q.push({u, d[u]}); } while(!q.empty()){ int u=q.top().u; int du=q.top().w; q.pop(); if(d[u]<du)continue; for(auto [v,w]:adj1[u]){ if(d[v]>du+w){ d[v]=du+w; q.push({v, d[v]}); } } } for(int i=0;i<m;i++){ e[i].w=min(d[e[i].u],d[e[i].v]); } sort(e,e+m); for(int i=0;i<m;i++){ int u=e[i].u,v=e[i].v,w=e[i].w; if(Find(u)!=Find(v)){ u=Find(u); v=Find(v); adj2[u].push_back({v, w}); adj2[v].push_back({u, w}); if(sz[u]<sz[v])swap(u,v); sz[u]+=sz[v]; r[v]=u; } } dfs(1,0); for(int j = 1; j<=20; ++j){ for(int i = 1; i<=n; ++i){ p[i][j]=p[p[i][j-1]][j-1]; dp[i][j] = min(dp[i][j-1], dp[p[i][j-1]][j-1]); } } cin>>t; while(t--){ int u,v; cin>>u>>v; cout<<lca(u, v)<<"\n"; } return 0; }

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

plan.cpp: In function 'void dfs(int, int)':
plan.cpp:30:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto[v,w]:adj2[u]){
      |             ^
plan.cpp: In function 'int main()':
plan.cpp:93:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         for(auto [v,w]:adj1[u]){
      |                  ^
#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...