oj.uz

Submission #547630

# Submission time Handle Problem Language Result Execution time Memory
547630 2022-04-11T06:27:23 Z Jomnoi Tree Rotations (POI11_rot) C++17
0 / 100
 177 ms 29788 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 4e5 + 10;

int n, cnt;
int L[MAX_N], R[MAX_N];
int fenwick[MAX_N];
vector <int> arr[MAX_N];
int sz[MAX_N];

void update(const int &idx, const int &val) {
    for(int i = idx; i < MAX_N; i += (i & -i)) {
        fenwick[i] += val;
    }
}

int query(const int &idx) {
    int res = 0;
    for(int i = idx; i >= 1; i -= (i & -i)) {
        res += fenwick[i];
    }
    return res;
}

int read_input() {
    int now;
    cin >> now;

    if(now == 0) {
        now = ++cnt;
        L[now] = read_input();
        R[now] = read_input();
        sz[now] = sz[L[now]] + sz[R[now]] + 1;
    }
    else {
        now += n;
        sz[now] = 1;
        L[now] = R[now] = -1;
    }
    return now;
}

long long dfs(const int &u, const bool &keep) {
    long long res = 0, inv = 0;
    if(L[u] == -1 and R[u] == -1) {
        arr[u].push_back(u - n);
        update(u - n, 1);
    }
    else {
        int v1 = L[u], v2 = R[u];
        if(sz[v1] < sz[v2]) {
            swap(v1, v2);
        }

        res = dfs(v1, true) + dfs(v2, false);

        swap(arr[u], arr[v1]);
        for(auto x : arr[v2]) {
            inv += query(n) - query(x);
        }
        for(auto x : arr[v2]) {
            arr[u].push_back(x);
            update(x, 1);
        }
        inv = min(inv, sz[v1] * sz[v2] - inv);
    }

    if(keep == false) {
        for(auto x : arr[u]) {
            update(x, -1);
        }
    }
    return res + inv;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    read_input();

    cout << dfs(1, false);
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 11732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 14012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 24724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 18336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 29788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 24944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 26012 KB Output isn't correct
2 Halted 0 ms 0 KB -