Submission #1067283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067283		trandangquang	Untitled (POI11_rot)	C++17	36 / 100	145 ms	65536 KiB

Main

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10