Submission #205699

#TimeUsernameProblemLanguageResultExecution timeMemory
205699ZwariowanyMarcinSightseeing (NOI14_sightseeing)C++14
25 / 25
3293 ms216584 KiB
#include <bits/stdc++.h> #define LL long long #define LD long double #define pb push_back #define mp make_pair #define ss(x) (int) x.size() #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl #define rep2(i, j, n) for (LL i = j; i <= n; ++i) #define rep(i, j, n) for (int i = j; i <= n; ++i) #define per(i, j, n) for (int i = n; j <= i; --i) #define boost cin.tie(0);ios_base::sync_with_stdio(0); #define vi vector <int> using namespace std; const int nax = 5e6 + 111; int n, m, q; int a, b, c; vector <pair<int, pair<int, int>>> ed; int ans[nax]; int p[nax]; vector <pair<int, int>> v[nax]; int find(int x) { if (x == p[x]) return x; return p[x] = find(p[x]); } void unia(int x, int y) { x = find(x); y = find(y); if (ss(v[x]) > ss(v[y])) swap(x, y); p[x] = y; for (auto it : v[x]) v[y].pb(it); } int main() { scanf ("%d%d%d", &n, &m, &q); rep(i, 1, m) { scanf ("%d%d%d", &a, &b, &c); ed.pb({c, {a, b}}); } sort(ed.begin(), ed.end()); rep(i, 1, q) { scanf ("%d", &a); v[a].pb({a, i}); } rep(i, 1, n) p[i] = i; per(i, 0, ss(ed) - 1) { int cost = ed[i].fi; int x = ed[i].se.fi; int y = ed[i].se.se; x = find(x); y = find(y); if (x == y) continue; if (find(1) != x) swap(x, y); if (find(1) == x) { p[y] = x; for (auto it : v[y]) ans[it.se] = cost; continue; } unia(x, y); } rep(i, 1, q) printf ("%d\n", ans[i]); return 0; }

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &m, &q);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", &a, &b, &c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...