Submission #892082

#TimeUsernameProblemLanguageResultExecution timeMemory
892082kh0iSjekira (COCI20_sjekira)C++17
110 / 110
37 ms7236 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } const int N = 1e5 + 3; struct Edge{ int u, v; ll w; bool operator < (const Edge &o) const { return w < o.w; } }; struct DSU{ vector<ll> p, sz, mx; int comp; void init(int n){ p.resize(n + 2, 0); sz.resize(n + 2, 0); mx.resize(n + 2, 0); comp = n; for(int i = 1; i <= n; ++i) p[i] = i, sz[i] = 1, mx[i] = 0; } int find_set(int u){ return u == p[u] ? u : p[u] = find_set(p[u]); } ll join_sets(int u, int v, ll x, ll y){ u = find_set(u), v = find_set(v); mx[u] = max(mx[u], x); mx[v] = max(mx[v], y); if(u == v) return 0; --comp; if(sz[u] < sz[v]) swap(u, v); ll res = mx[u] + mx[v]; p[v] = u; sz[u] += sz[v]; mx[u] = max(mx[u], mx[v]); return res; } } dsu; int n; ll a[N]; vector<Edge> e; void solve(){ cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i < n; ++i){ int u, v; cin >> u >> v; ll w = max(a[u], a[v]); e.push_back({u, v, w}); } sort(all(e)); dsu.init(n); ll res = 0; for(auto [u, v, w] : e) res += dsu.join_sets(u, v, a[u], a[v]); cout << res; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "paradigm" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

Compilation message (stderr)

sjekira.cpp: In function 'int32_t main()':
sjekira.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sjekira.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...