oj.uz

Submission #365162

# Submission time Handle Problem Language Result Execution time Memory
365162 2021-02-11T04:05:16 Z mohamedsobhi777 Sjekira (COCI20_sjekira) C++14
40 / 110
 1000 ms 2284 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;

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});
       }
       
       ll ans = 0;
       n--;
       while (n--)
       {
              int i = -1, j = -1, k = 2e9 + 1;
              for (auto u : ed)
              {
                     int fi = de.find(u.f);
                     int fj = de.find(u.s);
                     if (fi != fj && de.mx[fi] + de.mx[fj] < k)
                     {
                            k = de.mx[fi] + de.mx[fj];
                            i = u.f, j = u.s;
                     }
              }
              ans += k;
              de.link(i, j);
       }
       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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 2284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 11 ms 748 KB Output is correct
7 Correct 8 ms 748 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 10 ms 748 KB Output is correct
10 Correct 12 ms 748 KB Output is correct

Subtask #4
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 Execution timed out 1096 ms 2284 KB Time limit exceeded
7 Halted 0 ms 0 KB -