oj.uz

Submission #1067283

# Submission time Handle Problem Language Result Execution time Memory
1067283 2024-08-20T13:55:49 Z trandangquang Tree Rotations (POI11_rot) C++17
36 / 100
 145 ms 65536 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(u == -1) return;
    if(val[u] != 0) valN[u].eb(val[u]);

    dfs(ch[u].fi);
    dfs(ch[u].se);

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

    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:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14948 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 34048 KB Output is correct
2 Correct 7 ms 15448 KB Output is correct
3 Correct 28 ms 36600 KB Output is correct
4 Correct 47 ms 43576 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26196 KB Output is correct
2 Runtime error 105 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -