제출 #1055308

#제출 시각아이디문제언어결과실행 시간메모리
1055308vjudge1Evacuation plan (IZhO18_plan)C++17
100 / 100
391 ms62628 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define task "D" #define pa pair < int, int > #define fi first #define se second const int N = 2e5 + 1; const int INF = 1e18; const int mod = 1e9 + 3; int n, m, q, k, cur = 0; int a[N], d[N], p[N], ans[N]; set < int > se[N]; vector < pa > g[N]; void dijkstra() { fill(d + 1, d + N - 1, LLONG_MAX); cin >> k; set < pa > st; for(int i = 0; i < k; i++){ int x; cin >> x; d[x] = 0; st.insert({0, x}); } while(!st.empty()){ int v = st.begin()->se; st.erase(st.begin()); for(auto [to, w] : g[v]){ if (d[to] > d[v] + w){ st.erase({d[to], to}); d[to] = d[v] + w; st.insert({d[to], to}); } } } } int get(int v) { if (p[v] == v) return v; return p[v] = get(p[v]); } void merge(int v, int u) { v = get(v); u = get(u); if (v == u) return; p[u] = v; if(se[v].size() < se[u].size()){ se[v].swap(se[u]); } for(auto i : se[u]){ if(se[v].find(i) == se[v].end()){ se[v].insert(i); } else{ ans[i] = cur; se[v].erase(i); } } se[u].clear(); } bool cmp(int x, int y){ return d[x] > d[y]; } void read(){ cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y, w; cin >> x >> y >> w; g[x].push_back({y, w}); g[y].push_back({x, w}); } dijkstra(); cin >> q; for (int i = 1; i <= q; i++) { int s, t; cin >> s >> t; se[s].insert(i); se[t].insert(i); } for(int i = 1; i <= n; ++i){ a[i] = i; } sort(a + 1, a + n + 1, cmp); for(int i = 1; i <= n; ++i){ p[i] = i; } for(int i = 1; i <= n; ++i) { cur = d[a[i]]; for(auto [to, w] : g[a[i]]){ if(d[to] >= d[a[i]]){ merge(a[i], to); } } } for (int i = 1; i <= q; i++) { cout << ans[i] << '\n'; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen(task".INP","r")){ freopen(task".INP","r",stdin); freopen(task".OUT","w",stdout); } int t = 1; while(t--){ read(); } return 0; }

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

plan.cpp: In function 'int main()':
plan.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...