oj.uz

Submission #943614

# Submission time Handle Problem Language Result Execution time Memory
943614 2024-03-11T16:45:06 Z a_l_i_r_e_z_a Tree Rotations (POI11_rot) C++17
100 / 100
 177 ms 32460 KB 
// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 4e5 + 10;
const ll inf = 1e9 + 7;
ll n, nm, lc[maxn], rc[maxn], sz[maxn], a[maxn], nl[maxn], fen[maxn];
ll ans[maxn], res;
vector<ll> vec;

void input(ll v){
    sz[v] = 1;
    ll u; cin >> u;
    if(u){
        a[v] = u;
        nl[v] = 1;
        return;
    }
    lc[v] = ++nm;
    input(nm);
    sz[v] += sz[lc[v]];
    rc[v] = ++nm;
    input(nm);
    sz[v] += sz[rc[v]];
    nl[v] = nl[lc[v]] + nl[rc[v]];
}

ll get(ll i){
    ll rr = 0;
    for(; i; i &= i - 1) rr += fen[i];
    return rr;
}

void upd(ll i, ll x){
    for(; i <= n; i += i & -i) fen[i] += x;
}

void dfs2(ll v){
    if(lc[v] == -1){
        res += get(n) - get(a[v]);
        return;
    }
    dfs2(lc[v]);
    dfs2(rc[v]);
}

void dfs3(ll v){
    if(lc[v] == -1){
        upd(a[v], 1);
        vec.pb(a[v]);
        return;
    }
    dfs3(lc[v]);
    dfs3(rc[v]);
}

void reset(){
    for(auto u: vec) upd(u, -1);
    vec.clear();
}

void dfs(ll v){
    if(lc[v] == -1){
        upd(a[v], 1);
        vec.pb(a[v]);
        return;
    }
    if(sz[lc[v]] < sz[rc[v]]) swap(lc[v], rc[v]);
    dfs(rc[v]);
    reset();
    dfs(lc[v]);
    res = 0;
    ans[v] = ans[lc[v]] + ans[rc[v]];
    dfs2(rc[v]);
    ans[v] += min(nl[lc[v]] * nl[rc[v]] - res, res);
    dfs3(rc[v]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(ll i = 0; i <= 2 * n - 1; i++) lc[i] = rc[i] = -1;
    input(0);
    dfs(0);
    cout << ans[0] << '\n';

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12776 KB Output is correct
3 Correct 3 ms 13016 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 7 ms 15196 KB Output is correct
3 Correct 19 ms 15840 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16596 KB Output is correct
2 Correct 18 ms 17632 KB Output is correct
3 Correct 20 ms 18908 KB Output is correct
4 Correct 25 ms 18912 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26328 KB Output is correct
2 Correct 27 ms 24644 KB Output is correct
3 Correct 37 ms 23204 KB Output is correct
4 Correct 26 ms 22112 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 22740 KB Output is correct
2 Correct 44 ms 24184 KB Output is correct
3 Correct 37 ms 26324 KB Output is correct
4 Correct 37 ms 26068 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 28064 KB Output is correct
2 Correct 76 ms 26376 KB Output is correct
3 Correct 75 ms 26856 KB Output is correct
4 Correct 74 ms 26316 KB Output is correct
5 Correct 128 ms 25468 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26576 KB Output is correct
2 Correct 72 ms 31112 KB Output is correct
3 Correct 88 ms 29644 KB Output is correct
4 Correct 62 ms 31952 KB Output is correct
5 Correct 164 ms 26032 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 26816 KB Output is correct
2 Correct 68 ms 27640 KB Output is correct
3 Correct 119 ms 26060 KB Output is correct
4 Correct 86 ms 26576 KB Output is correct
5 Correct 77 ms 32460 KB Output is correct
6 Correct 177 ms 26056 KB Output is correct