제출 #40619

#제출 시각아이디문제언어결과실행 시간메모리
40619alenam0161Evacuation plan (IZhO18_plan)C++14
100 / 100
908 ms49996 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+7; vector<int> g[N],cost[N]; int di[N]; bool used[N]; int par[N]; int fpar(int v){ return v==par[v] ?v:par[v]=fpar(par[v]); } int up[N][25],val[N][25]; int tin[N],tout[N],ti=0; void dfs(int v,int p){ tin[v]=++ti; up[v][0]=p; val[v][0]=min(di[v],di[p]); for(int i=1;i<=20;++i){up[v][i]=up[up[v][i-1]][i-1];val[v][i]=min(val[v][i-1],val[up[v][i-1]][i-1]); } for(int to:g[v]){ if(to==p)continue; dfs(to,v); } tout[v]=++ti; } bool in(int v,int u){ return tin[v]<=tin[u]&&tout[u]<=tout[v]; } int get_ans(int u,int v){ int ans=1e9; for(int i=20;i>=0;i--){ if(in(u,up[v][i])==true){ ans=min(ans,val[v][i]); v=up[v][i]; } } return min(ans,di[u]); } int lca(int v,int u){ if(in(v,u))return v; if(in(u,v))return u; for(int i=20;i>=0;i--)if(in(up[v][i],u)==false)v=up[v][i]; return up[v][0]; } int ans(int v,int u){ int k=lca(u,v); return min(get_ans(k,v),get_ans(k,u)); } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ int u,v,c; scanf("%d%d%d",&u,&v,&c); g[u].push_back(v); g[v].push_back(u); cost[u].push_back(c); cost[v].push_back(c); } int k; scanf("%d",&k); memset(di,63,sizeof(di)); priority_queue<pair<int,int>> q; for(int i=1;i<=k;++i){ int l; scanf("%d",&l); di[l]=0; q.push({0,l}); } for(int i=1;i<=n;++i){ int v=-1; while(!q.empty()){ v=q.top().second;q.pop(); if(used[v]==false){ break; } } if(v==-1||used[v])break; used[v]=true; for(int j=0;j<g[v].size();++j){ int to=g[v][j]; int c=cost[v][j]; if(di[to]>di[v]+c){ di[to]=di[v]+c; q.push({-di[to],to}); } } } vector<pair<int,int>> ma; for(int i=1;i<=n;++i){ ma.push_back({di[i],i}); par[i]=i; } sort(ma.begin(),ma.end()); vector<pair<int,int>> kox; srand(107); memset(used,0,sizeof(used)); for(int i=ma.size()-1;i>=0;i--){ int v=ma[i].second; used[v]=true; for(int to:g[v]){ if(used[to]==false)continue; int x=fpar(v); int y=fpar(to); if(x!=y){ kox.push_back({v,to}); if(rand()&1){ par[x]=y; } else par[y]=x; } } } for(int i=0;i<=n;++i)g[i].clear(); for(pair<int,int> to:kox){ g[to.second].push_back(to.first); g[to.first].push_back(to.second); } /* for(int i=1;i<=n;++i){ cout<<di[i]<< " "<<i<<endl<<"kox:"; for(int to:g[i]){ cout<<to<<" "; } cout<<endl; } */ dfs(1,1); int query; scanf("%d",&query); for(int i=0;i<query;++i){ int u,v; scanf("%d%d",&u,&v); printf("%d\n",ans(u,v)); } return 0; }

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

plan.cpp: In function 'int main()':
plan.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[v].size();++j){
                     ~^~~~~~~~~~~~
plan.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&u,&v,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
plan.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&l);
         ~~~~~^~~~~~~~~
plan.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&query);
    ~~~~~^~~~~~~~~~~~~
plan.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&u,&v);
     ~~~~~^~~~~~~~~~~~~~
#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...