Submission #374358

#TimeUsernameProblemLanguageResultExecution timeMemory
374358VEGAnnSjekira (COCI20_sjekira)C++14
40 / 110
1089 ms2668 KiB
#include <bits/stdc++.h> #define MP make_pair #define PB push_back #define all(x) x.begin(),x.end() #define i3 array<int,3> #define pi3 pair<pair<int, int>, int> #define ft first #define sd second using namespace std; typedef long double ld; typedef long long ll; const ld E = 1e-9; const int oo = 2e9; const int N = 100100; vector<pi3> edgs; int n, pre[N], U[N], V[N]; bool mrk[N]; ll t[N], mx[N], ans = 0; int get(int x) { return (pre[x] == x ? x : pre[x] = get(pre[x])); } int get_val(int id){ return mx[get(U[id])] + mx[get(V[id])]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef _LOCAL freopen("in.txt","r",stdin); #endif // _LOCAL cin >> n; for (int i = 0; i < n; i++) { cin >> t[i]; pre[i] = i; mx[i] = t[i]; } for (int i = 1; i < n; i++){ int x, y; cin >> x >> y; x--; y--; U[i] = x; V[i] = y; // edgs.PB({t[x] + t[y], x, y}); // edgs.PB(MP(MP(t[x] + t[y], x), y)); } for (int it = 1; it < n; it++){ ll best = oo + 10, id = -1; for (int i = 1; i < n; i++){ if (mrk[i]) continue; ll cur = get_val(i); if (cur < best){ best = cur; id = i; } } mrk[id] = 1; ans += best; mx[get(U[id])] = max(mx[get(U[id])], mx[get(V[id])]); pre[get(V[id])] = get(U[id]); } // sort(all(edgs)); // // for (pi3 cr : edgs){ //// int x = cr[1], y = cr[2]; // int x = cr.ft.sd, y = cr.sd; // // x = get(x); // y = get(y); // // ans += mx[x]; // ans += mx[y]; // // mx[x] = max(mx[x], mx[y]); // pre[y] = x; // } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...