Submission #321550

#TimeUsernameProblemLanguageResultExecution timeMemory
321550arujbansalSightseeing (NOI14_sightseeing)C++17
25 / 25
2276 ms202728 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) #define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout) #define seed() srand(chrono::steady_clock::now().time_since_epoch().count()) #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int) (x).size() #define lc(i) 2*i #define rc(i) 2*i+1 //#define int long long using namespace std; using ll = long long; using ii = pair<int, int>; using vii = vector<ii>; using vi = vector<int>; using vvi = vector<vi>; using vb = vector<bool>; using vvb = vector<vb>; ll rng() { ll a = rand(); ll b = rand(); return a * (RAND_MAX + 1ll) + b; } const int N = 5e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5; vii g[N]; int mn[N]; struct DSU { int n; vector<int> par, s; void init(int x) { n = x; par.resize(n); iota(all(par), 0); s.assign(n, 1); } int get(int x) { if (par[x] == x) return x; return par[x] = get(par[x]); } bool unite(int x, int y) { x = get(x); y = get(y); if (x == y) return false; if (s[x] < s[y]) swap(x, y); s[x] += s[y]; par[y] = x; return true; } int getSz(int x) { x = get(x); return s[x]; } }; struct Edge { int u, v, w; Edge(int u, int v, int w) : u(u), v(v), w(w) {} bool operator<(const Edge &other) const { return w > other.w; } }; void dfs(int u = 0, int p = -1) { for (const auto &[v, w] : g[u]) { if (v == p) continue; mn[v] = min(mn[u], w); dfs(v, u); } } void solve() { int n, m, q; cin >> n >> m >> q; vector<Edge> edges; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; edges.eb(u, v, w); } sort(all(edges)); DSU sites; sites.init(n); for (const auto &[u, v, w] : edges) { if (!sites.unite(u, v)) continue; g[u].eb(v, w); g[v].eb(u, w); } mn[0] = INF; dfs(); while (q--) { int v; cin >> v; v--; cout << mn[v] << "\n"; } } signed main() { FAST_IO; #ifdef arujbansal_local setIO("input.txt", "output.txt"); #endif seed(); int tc = 1; // cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...