oj.uz

Submission #391273

# Submission time Handle Problem Language Result Execution time Memory
391273 2021-04-18T11:25:53 Z MrRobot_28 Sjekira (COCI20_sjekira) C++17
110 / 110
 161 ms 35524 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
#define int long long
#define ld long double
const int N = 3e5 + 100;
int dsu[N];
int val[N];
int rang[N];
vector <pair <int, int> > vec[N];
int pred(int a)
{
    if(a == dsu[a]) return a;
    return dsu[a] = pred(dsu[a]);
}
void unite(int a, int b)
{
    a = pred(a);
    b = pred(b);
    if(rang[b] < rang[a])
    {
        swap(a, b);
    }
    dsu[b] = a;
    rang[a] += rang[b];
    val[a] = max(val[a], val[b]);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <pair <int, int> > a(n);
    vector <set <pair <int, int> > > st(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].X;
        val[i] = a[i].X;
        a[i].Y = i;
        dsu[i] = i;
        rang[i] = 1;
    }
    sort(a.begin(), a.end());
    vector <vector <int> > g(n);
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a>> b;
        a--;
        b--;
        vec[a].push_back({a, b});
        vec[b].push_back({b, a});
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 0; i < n; i++)
    {
        for(auto to : g[i])
        {
            if(val[to] > val[i] || val[to] == val[i] && to > i)
            {
                st[i].insert({val[to], to});
            }
        }
    }
    ll s = 0;
    for(int i = 0; i < n; i++)
    {
        int minto = -1;
        int v = a[i].Y;
        if(sz(st[v]) != 0)
        {
            pair <int, int> t = *st[v].begin();
            st[v].erase(t);
            s += t.X + val[v];
           // cout << t.X << " " << val[v] << "\n";
            if(sz(st[t.Y]) < sz(st[v]))
            {
                swap(st[t.Y], st[v]);
            }
            for(auto p : st[v])
            {
                st[t.Y].insert(p);
            }
        }
    }
    cout << s;
    return 0;
}

Compilation message

sjekira.cpp: In function 'int main()':
sjekira.cpp:65:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   65 |             if(val[to] > val[i] || val[to] == val[i] && to > i)
      |                                    ~~~~~~~~~~~~~~~~~~^~~~~~~~~
sjekira.cpp:74:13: warning: unused variable 'minto' [-Wunused-variable]
   74 |         int minto = -1;
      |             ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 27708 KB Output is correct
2 Correct 63 ms 22852 KB Output is correct
3 Correct 60 ms 22340 KB Output is correct
4 Correct 67 ms 24072 KB Output is correct
5 Correct 111 ms 32400 KB Output is correct
6 Correct 88 ms 32324 KB Output is correct
7 Correct 67 ms 30784 KB Output is correct
8 Correct 60 ms 28716 KB Output is correct
9 Correct 42 ms 21316 KB Output is correct
10 Correct 79 ms 34540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7328 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Correct 7 ms 7496 KB Output is correct
8 Correct 6 ms 7572 KB Output is correct
9 Correct 6 ms 7628 KB Output is correct
10 Correct 6 ms 7628 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7328 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 84 ms 27708 KB Output is correct
7 Correct 63 ms 22852 KB Output is correct
8 Correct 60 ms 22340 KB Output is correct
9 Correct 67 ms 24072 KB Output is correct
10 Correct 111 ms 32400 KB Output is correct
11 Correct 88 ms 32324 KB Output is correct
12 Correct 67 ms 30784 KB Output is correct
13 Correct 60 ms 28716 KB Output is correct
14 Correct 42 ms 21316 KB Output is correct
15 Correct 79 ms 34540 KB Output is correct
16 Correct 7 ms 7632 KB Output is correct
17 Correct 7 ms 7496 KB Output is correct
18 Correct 6 ms 7572 KB Output is correct
19 Correct 6 ms 7628 KB Output is correct
20 Correct 6 ms 7628 KB Output is correct
21 Correct 29 ms 13944 KB Output is correct
22 Correct 26 ms 12876 KB Output is correct
23 Correct 147 ms 34140 KB Output is correct
24 Correct 96 ms 26564 KB Output is correct
25 Correct 96 ms 26288 KB Output is correct
26 Correct 63 ms 19864 KB Output is correct
27 Correct 70 ms 22212 KB Output is correct
28 Correct 120 ms 27476 KB Output is correct
29 Correct 72 ms 20976 KB Output is correct
30 Correct 161 ms 35524 KB Output is correct