Submission #1020589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1020589	2024-07-12T07:19:13 Z	BuzzyBeez	Tree Rotations (POI11_rot)	C++17	100 / 100	209 ms	36832 KB

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5;

int a[N + 8];
int adj[N + 8][2];
vector<int> _list[N + 8];
int sz[N + 8];

int n, tmp, id = 1, x;
void input() {
	cin >> x;
	if (x) {_list[id].push_back(x); ++sz[id]; a[id] = x; return;}
	int t = id;
	adj[t][0] = id + 1;
	++id; input();
	adj[t][1] = id + 1;
	++id; input();
}

void DFS_sz(int u, int p) {
	if (!adj[u][0]) return;
	DFS_sz(adj[u][0], u); sz[u] += sz[adj[u][0]];
	DFS_sz(adj[u][1], u); sz[u] += sz[adj[u][1]];
}

struct Binary_Indexed_Tree {
	vector<int> BIT;
	
	Binary_Indexed_Tree() {BIT.assign(N / 2 + 8, 0);}
	
	int pt;
	void update(int u, int v) {
		pt = u;
		while (pt <= N / 2) {
			BIT[pt] += v;
			pt += pt & -pt;
		}
	}
	
	int res;
	int pf(int p) {
		if (p <= 0) return 0;
		res = 0; pt = p;
		while (pt) {
			res += BIT[pt];
			pt -= pt & -pt;
		}
		return res;
	}
	
	int range(int l, int r) {
		if (l > r) return 0;
		return pf(r) - pf(l - 1);
	}
} tree;

long long costLR, costRL, ans = 0;
void DFS(int u, int p) {
	if (sz[u] > 1) { 
		int L = adj[u][0], R = adj[u][1];
		if (sz[L] < sz[R]) swap(L, R);
		// cout << u << " -> " << R << endl;
		DFS(R, u);
		for (int item : _list[R]) tree.update(item, -1);
		// cout << u << " -> " << L << endl;
		DFS(L, u);
		costLR = costRL = 0;
		for (int item : _list[R]) costLR += tree.range(item + 1, n), costRL += tree.range(1, item - 1);
		ans += min(costLR, costRL);
		// cout << u << ' ' << costLR << ' ' << costRL << '\n';
		for (int item : _list[R]) tree.update(item, +1);
		for (int v : {L, R}) {
			if (_list[u].size() < _list[v].size()) swap(_list[u], _list[v]);
			for (int item : _list[v]) _list[u].push_back(item);
		}
	}
	if (a[u]) tree.update(a[u], +1);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n; input();
	DFS_sz(1, 0);
	DFS(1, 0); cout << ans;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	10588 KB	Output is correct
2	Correct	4 ms	10588 KB	Output is correct
3	Correct	5 ms	10588 KB	Output is correct
4	Correct	5 ms	10588 KB	Output is correct
5	Correct	6 ms	10588 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10584 KB	Output is correct
2	Correct	5 ms	10588 KB	Output is correct
3	Correct	7 ms	10612 KB	Output is correct
4	Correct	4 ms	10588 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	10584 KB	Output is correct
2	Correct	6 ms	10588 KB	Output is correct
3	Correct	5 ms	10588 KB	Output is correct
4	Correct	5 ms	10588 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	11096 KB	Output is correct
2	Correct	7 ms	10856 KB	Output is correct
3	Correct	7 ms	11100 KB	Output is correct
4	Correct	6 ms	11404 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	12376 KB	Output is correct
2	Correct	13 ms	11884 KB	Output is correct
3	Correct	31 ms	13860 KB	Output is correct
4	Correct	10 ms	12376 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	15440 KB	Output is correct
2	Correct	29 ms	16932 KB	Output is correct
3	Correct	31 ms	18780 KB	Output is correct
4	Correct	31 ms	18820 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	24548 KB	Output is correct
2	Correct	39 ms	22100 KB	Output is correct
3	Correct	60 ms	20440 KB	Output is correct
4	Correct	38 ms	18148 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	19520 KB	Output is correct
2	Correct	53 ms	22232 KB	Output is correct
3	Correct	52 ms	26316 KB	Output is correct
4	Correct	60 ms	26200 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	31248 KB	Output is correct
2	Correct	112 ms	29132 KB	Output is correct
3	Correct	83 ms	27980 KB	Output is correct
4	Correct	102 ms	27728 KB	Output is correct
5	Correct	164 ms	29388 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	26200 KB	Output is correct
2	Correct	98 ms	35664 KB	Output is correct
3	Correct	121 ms	34256 KB	Output is correct
4	Correct	85 ms	36832 KB	Output is correct
5	Correct	209 ms	32592 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	26764 KB	Output is correct
2	Correct	87 ms	29540 KB	Output is correct
3	Correct	145 ms	30280 KB	Output is correct
4	Correct	107 ms	29028 KB	Output is correct
5	Correct	80 ms	36808 KB	Output is correct
6	Correct	196 ms	33284 KB	Output is correct

Submission #1020589

Compilation message