제출 #50846

#제출 시각아이디문제언어결과실행 시간메모리
50846NicksechkoEvacuation plan (IZhO18_plan)C++14
100 / 100
1070 ms57100 KiB
#include <bits/stdc++.h> using namespace std; #ifdef WIN32 #define I64 "%I64d" #else #define I64 "%lld" #endif typedef long long ll; #define f first #define s second #define mp make_pair #define pb push_back #define all(s) s.begin(), s.end() #define sz(s) (int(s.size())) #define fname "a" #define MAXN 100001 #define MAXM 500005 const int INF = int(1e9); int n, m, k, qq; vector < pair<int, int> > g[MAXN]; int d[MAXN]; priority_queue < pair<int, int> > q; int ans[MAXN]; vector < pair<int, pair<int, int> > > e; unordered_set <int> u[MAXN]; int c[MAXN]; inline int getp(int v) { return c[v] == v ? v : c[v] = getp(c[v]); } int main() { #ifdef LOCAL freopen(fname".in", "r", stdin); freopen(fname".out", "w", stdout); #endif scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { int v1, v2, cost; scanf("%d%d%d", &v1, &v2, &cost); --v1, --v2; g[v1].pb({v2, cost}); g[v2].pb({v1, cost}); } for (int i = 0; i < n; ++i) { d[i] = INF; } scanf("%d", &k); for (int i = 0; i < k; ++i) { int x; scanf("%d", &x); --x; d[x] = 0; q.push({-d[x], x}); } while(!q.empty()) { int dist = -q.top().f; int v = q.top().s; q.pop(); if (dist != d[v]) continue; for (const auto& t : g[v]) { int v2 = t.f; int cost = t.s; if (d[v2] > d[v] + cost) { d[v2] = d[v] + cost; q.push({-d[v2], v2}); } } } scanf("%d", &qq); for (int i = 0; i < qq; ++i) { int v1, v2; scanf("%d%d", &v1, &v2); --v1, --v2; u[v1].insert(i); u[v2].insert(i); } for (int i = 0; i < n; ++i) { c[i] = i; for (const auto& ed : g[i]) { e.pb(mp(min(d[i], d[ed.f]), mp(i, ed.f))); } } sort(all(e)); for (int i = sz(e) - 1; i >= 0; --i) { int cost = e[i].f; int v1 = getp(e[i].s.f); int v2 = getp(e[i].s.s); if (v1 == v2) continue; if (sz(u[v1]) < sz(u[v2])) swap(v1, v2); for (const int& ind : u[v2]) { if (u[v1].count(ind)) { ans[ind] = cost; u[v1].erase(ind); } else { u[v1].insert(ind); } } c[v2] = v1; } for (int i = 0; i < qq; ++i) { printf("%d\n", ans[i]); } return 0; }

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

plan.cpp: In function 'int main()':
plan.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v1, &v2, &cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &qq);
  ~~~~~^~~~~~~~~~~
plan.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v1, &v2);
   ~~~~~^~~~~~~~~~~~~~~~~~
#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...