oj.uz

답안 #1067299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067299 2024-08-20T14:16:34 Z trandangquang Tree Rotations (POI11_rot) C++17
36 / 100
 126 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 = 1e6+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
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27224 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 4 ms 27224 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 5 ms 27996 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 46172 KB Output is correct
2 Correct 9 ms 27740 KB Output is correct
3 Correct 33 ms 48980 KB Output is correct
4 Correct 39 ms 55888 KB Output is correct

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 35924 KB Output is correct
2 Runtime error 60 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 126 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -