oj.uz

Submission #365167

# Submission time Handle Problem Language Result Execution time Memory
365167 2021-02-11T04:22:59 Z mohamedsobhi777 Sjekira (COCI20_sjekira) C++14
110 / 110
 121 ms 6380 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n;

struct dsu
{
       int fat[N];
       int mx[N];
       dsu()
       {
              iota(fat, fat + N, 0);
       }
       int find(int x) { return fat[x] = (x == fat[x] ? x : find(fat[x])); }
       void link(int u, int v)
       {
              u = find(u), v = find(v);
              mx[v] = max(mx[v], mx[u]);
              fat[u] = v;
       }
       bool same(int u, int v)
       {
              return find(u) == find(v);
       }
} de;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pr;

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       for (int i = 1; i <= n; ++i)
              cin >> de.mx[i];

       vii ed;

       for (int i = 0; i < n - 1; ++i)
       {
              int u, v;
              cin >> u >> v;
              ed.pb({u, v});
              pr.push({de.mx[u] + de.mx[v], {u, v}});
       }
       ll ans = 0;
       while (sz(pr))
       {
              pair<int, pii> tp = pr.top();
              pr.pop();
              if (de.same(tp.s.f, tp.s.s))
              {
                     continue;
              }
              if (de.mx[de.find(tp.s.f)] + de.mx[de.find(tp.s.s)] != tp.f)
              {
                     pr.push({de.mx[de.find(tp.s.f)] + de.mx[de.find(tp.s.s)], tp.s});
                     continue;
              }
              ans += tp.f;
              de.link(tp.s.f, tp.s.s);
       }
       cout << ans;
       return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3184 KB Output is correct
2 Correct 43 ms 3572 KB Output is correct
3 Correct 43 ms 3572 KB Output is correct
4 Correct 49 ms 4592 KB Output is correct
5 Correct 74 ms 5392 KB Output is correct
6 Correct 43 ms 6124 KB Output is correct
7 Correct 38 ms 5104 KB Output is correct
8 Correct 35 ms 4988 KB Output is correct
9 Correct 23 ms 3572 KB Output is correct
10 Correct 44 ms 6380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 58 ms 3184 KB Output is correct
7 Correct 43 ms 3572 KB Output is correct
8 Correct 43 ms 3572 KB Output is correct
9 Correct 49 ms 4592 KB Output is correct
10 Correct 74 ms 5392 KB Output is correct
11 Correct 43 ms 6124 KB Output is correct
12 Correct 38 ms 5104 KB Output is correct
13 Correct 35 ms 4988 KB Output is correct
14 Correct 23 ms 3572 KB Output is correct
15 Correct 44 ms 6380 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 23 ms 1988 KB Output is correct
22 Correct 23 ms 1856 KB Output is correct
23 Correct 117 ms 5104 KB Output is correct
24 Correct 78 ms 4740 KB Output is correct
25 Correct 75 ms 4592 KB Output is correct
26 Correct 47 ms 2936 KB Output is correct
27 Correct 58 ms 3344 KB Output is correct
28 Correct 121 ms 4336 KB Output is correct
29 Correct 66 ms 2808 KB Output is correct
30 Correct 121 ms 5504 KB Output is correct