oj.uz

Submission #1067290

# Submission time Handle Problem Language Result Execution time Memory
1067290 2024-08-20T14:02:28 Z trandangquang Tree Rotations (POI11_rot) C++17
0 / 100
 24 ms 21336 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ii pair <int, int>
#define fi first
#define se second
#define eb emplace_back
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()

using namespace std;

const int mxN = 5e5+5;
const int mxL = 2e5+5;

int n, val[mxN], cur, ans;
ii ch[mxN];
vector <int> valN[mxN];

int newNode() {
    return ++cur;
}

void input(int node) {
    int x; cin >> x;

    if(x == 0) {
        int lfN = newNode();
        input(lfN);
        int rtN = newNode();
        input(rtN);

        ch[node] = {lfN, rtN};
    }
    else {
        val[node] = x;
        ch[node] = {-1, -1};
    }
}

void dfs(int u) {
    if(val[u] != 0) valN[u].eb(val[u]);

    if(ch[u].fi == -1 || ch[u].se == -1) return;
    dfs(ch[u].fi); dfs(ch[u].se);

    valN[u].resize(sz(valN[ch[u].fi]) + sz(valN[ch[u].se]));
    merge(all(valN[ch[u].fi]), all(valN[ch[u].se]), valN[u].begin());

    int lr = 0;
    for(int i:valN[ch[u].se]) {
        int pos = upper_bound(all(valN[ch[u].fi]), i) - valN[ch[u].fi].begin();
        lr += sz(valN[ch[u].fi]) - pos;
    }

    int rl = 0;
    for(int i:valN[ch[u].fi]) {
        int pos = upper_bound(all(valN[ch[u].se]), i) - valN[ch[u].se].begin();
        rl += sz(valN[ch[u].se]) - pos;
    }
    ans = ans + min(lr, rl);
}

int main() {
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    cur = 1; input(1);
//    dfs(1);
    cout << ans;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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