Submission #44150

#TimeUsernameProblemLanguageResultExecution timeMemory
44150wasylSightseeing (NOI14_sightseeing)C++11
15 / 25
3543 ms176644 KiB
#include <bits/stdc++.h> #ifndef dbg #define dbg(...) #endif #define all(x) begin(x), end(x) #define rsz(...) resize(__VA_ARGS__) #define psh(...) push_back(__VA_ARGS__) #define emp(...) emplace_back(__VA_ARGS__) #define prt(...) print(cout, __VA_ARGS__) #define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__) #define dprt(...) dbg(print(cerr,__VA_ARGS__)) #define ddmp(...) dbg(dmp(__VA_ARGS__)) using namespace std;using ll=long long; template<typename t>using V=vector<t>; template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';} template<typename t, typename... A>void print (ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);} constexpr int MaxK = 1e5; constexpr int MaxN = 5e5; int n, m, q; int odp[MaxN + 1], siz[MaxN + 1], lid[MaxN + 1]; V< pair< int, int > > ilo[MaxK + 1]; V< pair< int, int > > gr[MaxN + 1]; inline int find (int v) { return lid[v] == lid[lid[v]]? lid[v] : lid[v] = find(lid[v]); } inline void join (int p, int q) { p = find(p); q = find(q); if (siz[p] < siz[q]) swap(p, q); siz[p] += siz[q]; lid[q] = p; } inline void dfs (int v, int o, int r = INT_MAX) { odp[v] = r; for (auto& p : gr[v]) if (p.first != o) dfs(p.first, v, min(r, p.second)); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> q; for (int i = 0; i < m; ++i) { int p, q, k; cin >> p >> q >> k; ilo[k].psh({p, q}); } for (int i = 1; i <= n; ++i) lid[i] = i; for (int i = MaxK; i >= 0; --i) { for (auto& v : ilo[i]) if (find(v.first) != find(v.second)) { join(v.first, v.second); gr[v.first].psh({v.second, i}); gr[v.second].psh({v.first, i}); } ilo[i].clear(); ilo[i].shrink_to_fit(); } dfs(1, 1); for (int i = 0; i < q; ++i) { int p; cin >> p; prt(odp[p]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...