제출 #344281

#제출 시각아이디문제언어결과실행 시간메모리
344281jenkinsserEvacuation plan (IZhO18_plan)C++17
100 / 100
1024 ms54296 KiB
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define st first #define nd second #define pii pair<int,int> #define N 100005 #define INF 1e9+5 #define sp " " #define endl "\n" #define fastio() ios_base::sync_with_stdio(0);cin.tie(0); #define all(x) (x).begin(),(x).end() #define ll long long #define int ll using namespace std; int n,m,dan[N],k,q,par[N],vis[N],ans[N]; vector<pii> g[N]; set<int> s[N]; set<pii> st; bool flag; int get_parent(int u){ if(par[u]==u) return u; return par[u]=get_parent(par[u]); } void solve(int u,int v){ int U=get_parent(u); int V=get_parent(v); if(U==V){ return; } if(s[U].size()>s[V].size()){ swap(U,V); } par[U]=V; while(s[U].size()!=0){ int cur= *(s[U].begin()); s[U].erase(s[U].begin()); flag=s[V].erase(cur); if(flag){ ans[cur]=dan[v]; } else{ s[V].insert(cur); } } } int32_t main(){ ios_base::sync_with_stdio(0),cin.tie(0); cin >> n >> m; for(int i=1;i<=n;i++){ dan[i]=INF; par[i]=i; } for(int i=1;i<=m;i++){ int u,v,w; cin >> u >> v >> w; g[u].pb(mp(v,w)); g[v].pb(mp(u,w)); } cin >> k; for(int i=1;i<=k;i++){ int x; cin >> x; dan[x]=0; st.insert({0,x}); } while(!st.empty()){ int cur=(st.begin()->nd); st.erase(st.begin()); for(int i=0;i<g[cur].size();i++){ int nei=g[cur][i].st; int edge=g[cur][i].nd; if(dan[nei]>dan[cur]+edge){ st.erase({dan[nei],nei}); dan[nei]=dan[cur]+edge; st.insert({dan[nei],nei}); } } } cin >> q; for(int i=1;i<=q;i++){ int u,v; cin >> u >> v; s[u].insert(i); s[v].insert(i); } vector<pii> vec; for(int i=1;i<=n;i++){ vec.pb(mp(dan[i],i)); } sort(vec.begin(),vec.end()); for(int i=n-1;i>=0;i--){ int cur=vec[i].nd; for(int j=0;j<g[cur].size();j++){ int nei=g[cur][j].st; if(dan[nei]>=dan[cur]) solve(nei,cur); } } for(int i=1;i<=q;i++){ cout << ans[i] << endl; } }

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

plan.cpp: In function 'int32_t main()':
plan.cpp:75:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0;i<g[cur].size();i++){
      |                     ~^~~~~~~~~~~~~~
plan.cpp:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<g[cur].size();j++){
      |                     ~^~~~~~~~~~~~~~
#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...