oj.uz

Submission #952321

# Submission time Handle Problem Language Result Execution time Memory
952321 2024-03-23T14:21:42 Z serifefedartar Tree Rotations (POI11_rot) C++17
100 / 100
 370 ms 41812 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 998244353;
const ll MAXN = 2e5 + 100;

vector<vector<int>> graph;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> st[MAXN];
int now = 0;
ll ans = 0;

int dfs() {
    int q; cin >> q;
    if (q == 0) {
        int x = dfs();
        int y = dfs();

        if (st[y].size() > st[x].size())
            swap(x, y);

        ll all = st[x].size() * 1LL * st[y].size();
        ll nw = 0;
        for (auto u : st[y])
            nw += st[x].order_of_key(u);
        for (auto u : st[y])
            st[x].insert(u);
        st[y].clear();
        ans += min(nw, all - nw);
        return x;
    } else {
        now++;
        st[now].insert(q);
        return now;
    }
}

int main() {
    fast
    int leaves; 
    cin >> leaves;

    dfs();
    cout << ans << "\n";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15960 KB Output is correct
2 Correct 12 ms 15964 KB Output is correct
3 Correct 10 ms 15960 KB Output is correct
4 Correct 10 ms 15960 KB Output is correct
5 Correct 10 ms 15964 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15964 KB Output is correct
2 Correct 12 ms 16076 KB Output is correct
3 Correct 10 ms 15984 KB Output is correct
4 Correct 11 ms 15960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15960 KB Output is correct
2 Correct 11 ms 15964 KB Output is correct
3 Correct 12 ms 15964 KB Output is correct
4 Correct 10 ms 16012 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16476 KB Output is correct
2 Correct 14 ms 16352 KB Output is correct
3 Correct 12 ms 16732 KB Output is correct
4 Correct 12 ms 16732 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18248 KB Output is correct
2 Correct 24 ms 16732 KB Output is correct
3 Correct 66 ms 18072 KB Output is correct
4 Correct 19 ms 17756 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 19224 KB Output is correct
2 Correct 56 ms 21600 KB Output is correct
3 Correct 60 ms 23712 KB Output is correct
4 Correct 54 ms 23632 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 29816 KB Output is correct
2 Correct 69 ms 27396 KB Output is correct
3 Correct 92 ms 22608 KB Output is correct
4 Correct 72 ms 21352 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22056 KB Output is correct
2 Correct 100 ms 24144 KB Output is correct
3 Correct 93 ms 31592 KB Output is correct
4 Correct 95 ms 31572 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 33360 KB Output is correct
2 Correct 166 ms 28212 KB Output is correct
3 Correct 161 ms 30400 KB Output is correct
4 Correct 177 ms 29264 KB Output is correct
5 Correct 303 ms 28752 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 28036 KB Output is correct
2 Correct 174 ms 40200 KB Output is correct
3 Correct 212 ms 32592 KB Output is correct
4 Correct 156 ms 41812 KB Output is correct
5 Correct 370 ms 31056 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 31572 KB Output is correct
2 Correct 179 ms 28632 KB Output is correct
3 Correct 267 ms 28244 KB Output is correct
4 Correct 222 ms 33364 KB Output is correct
5 Correct 163 ms 39508 KB Output is correct
6 Correct 311 ms 31712 KB Output is correct