제출 #545315

#제출 시각아이디문제언어결과실행 시간메모리
545315Ai7081Evacuation plan (IZhO18_plan)C++17
100 / 100
1370 ms41820 KiB
#include <bits/stdc++.h> using namespace std; const bool debug = 1; const int N = 100005; const int inf = 1e9; struct node{ int dis, v; bool operator < (const node &o) const { return dis > o.dis; } }; int n, m, q, a, b, c, dis[N], l[N], r[N], g[N]; pair<int, int> que[N]; vector<pair<int, int>> adj[N], ord; vector<int> test[N]; priority_queue<node> pq; bool mark[N]; int findg(int x) { if (g[x] == x) return x; return g[x] = findg(g[x]); } int main() { scanf(" %d %d", &n, &m); while (m--) { scanf(" %d %d %d", &a, &b, &c); adj[a].push_back({b, c}); adj[b].push_back({a, c}); } fill_n(dis, N, inf); scanf(" %d", &a); while (a--) { scanf(" %d", &b); pq.push({0, b}); dis[b] = 0; } scanf(" %d", &q); for (int i=0; i<q; i++) scanf(" %d %d", &que[i].first, &que[i].second); while (!pq.empty()) { int v = pq.top().v, d = pq.top().dis; pq.pop(); if (mark[v]) continue; mark[v] = true; for (auto [to, w] : adj[v]) { if (!mark[to] && dis[to] > d+w) { dis[to] = d+w; pq.push({dis[to], to}); } } } for (int i=1; i<=n; i++) ord.push_back({dis[i], i}); sort(ord.begin(), ord.end(), greater<pair<int, int>>()); bool con = true; fill_n(r, N, n-1); while (con) { con = false; fill_n(test, N, vector<int>()); fill_n(mark, N, false); for (int i=1; i<=n; i++) g[i] = i; for (int i=0; i<q; i++) { if (l[i] != r[i]) { test[(l[i]+r[i])/2].push_back(i); con = true; } } for (int i=0; i<n; i++) { int v = ord[i].second; mark[v] = true; for (auto [to, w] : adj[v]) if (mark[to]) g[findg(to)] = findg(v); for (auto it : test[i]) { if (findg(que[it].first) == findg(que[it].second)) r[it] = i; else l[it] = i+1; } } } for (int i=0; i<q; i++) printf("%d\n", ord[l[i]].first); return 0; } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */

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

plan.cpp: In function 'int main()':
plan.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf(" %d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d", &a);
      |     ~~~~~^~~~~~~~~~~
plan.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %d", &b);
      |         ~~~~~^~~~~~~~~~~
plan.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf(" %d", &q);
      |     ~~~~~^~~~~~~~~~~
plan.cpp:40:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for (int i=0; i<q; i++) scanf(" %d %d", &que[i].first, &que[i].second);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...