Submission #119524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
119524	2019-06-21T10:52:44 Z	popovicirobert	Tree Rotations (POI11_rot)	C++14	0 / 100	152 ms	11888 KB

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

/*
const int MOD = ;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}
*/

using namespace std;

//ifstream fin("B.in");
//ofstream fout("B.out");

const int MAXN = (int) 4e5;

int idl[MAXN + 1], idr[MAXN + 1], sz;
int son[MAXN + 1][2];
vector <int> arr;

int read(int &id) {
    int x, root = id;
    cin >> x;

    if(x == 0) {
        int a = read(++id), b = read(++id);
        son[root][0] = a, son[root][1] = b;
        idl[root] = idl[a], idr[root] = idr[b];
    }
    else {
        idl[root] = idr[root] = ++sz;
        arr.push_back(x);
    }

    return root;
}

int aib[MAXN + 1], n;

inline void update(int pos, int val) {
    for(int i = pos; i <= n; i += lsb(i)) {
        aib[i] += val;
    }
}

inline int query(int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lsb(i)) {
        ans += aib[i];
    }
    return ans;
}

vector <int> stk;
bool vis[MAXN + 1];
ll tot;

void dfs(int nod) {

    vis[nod] = 1;

    int a = son[nod][0], b = son[nod][1];
    if(idr[b] - idl[b] > idr[a] - idl[a]) {
        swap(a, b);
    }

    if(a == 0 && b == 0) {
        update(arr[idl[nod]], 1);
        stk.push_back(arr[idl[nod]]);
        return ;
    }

    dfs(a);

    ll cur = 0;
    for(int i = idl[b]; i <= idr[b]; i++) {
        cur += query(n) - query(arr[i]);
    }
    for(int i = idl[b]; i <= idr[b]; i++) {
        update(arr[i], 1);
        stk.push_back(arr[i]);
    }

    int len = idr[a] + idr[b] - idl[a] - idl[b] + 2;
    tot += min(cur, 1LL * len * (len - 1) / 2 - cur);

}

int main() {
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    arr.resize(1);
    int id = 1;
    int root = read(id);

    for(i = 1; i <= id; i++) {
        if(vis[i]) {
            continue;
        }
        dfs(i);

        for(auto it : stk) {
            update(it, -1);
        }

        stk.clear();
    }

    cout << tot;

    //fin.close();
    //fout.close();
    return 0;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:114:9: warning: unused variable 'root' [-Wunused-variable]
     int root = read(id);
         ^~~~

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	384 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	384 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	384 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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