oj.uz

Submission #1115160

# Submission time Handle Problem Language Result Execution time Memory
1115160 2024-11-20T07:26:47 Z VectorLi Tree Rotations (POI11_rot) C++17
100 / 100
 839 ms 53668 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define I64 long long
 
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int N = (int) 2E5;
const int V = N * 2 - 1;
 
int n;
int e[V][2];
 
int t;
map<int, ordered_set<int>> s;
 
int build(int u) {
	int p = t;
	t = t + 1;
	int x;
	cin >> x;
	if (x == 0) {
		e[u][0] = build(t);
		e[u][1] = build(t);
	} else {
		s[u].insert(x);
	}
	return p;
} 
 
I64 x;
 
void DFS(int u) {
	if (e[u][0] >= 0) {
		int v[2];
		v[0] = e[u][0];
		v[1] = e[u][1];
		DFS(v[0]);
		DFS(v[1]);
		if (s[v[0]].size() < s[v[1]].size()) {
			s[v[0]].swap(s[v[1]]);
		}
		I64 a = 0, b = 0;
		for (auto x : s[v[1]]) {
			a = a + (int) s[v[0]].order_of_key(x);
			b = b + (int) (s[v[0]].size()) - (int) s[v[0]].order_of_key(x);
		}
		s[u].swap(s[v[0]]);
		x = x + min(a, b);
		for (auto x : s[v[1]]) {
			s[u].insert(x);
		}
		s.erase(v[0]);
		s.erase(v[1]);
	}
}
 
void solve() {
	cin >> n;
	n = n * 2 - 1;
	for (int i = 0; i < n; i++) {
		e[i][0] = 0 - 1;
		e[i][1] = 0 - 1;
	}
	build(0);
	DFS(0);
	cout << x << "\n";
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1616 KB Output is correct
2 Correct 8 ms 1256 KB Output is correct
3 Correct 6 ms 1616 KB Output is correct
4 Correct 6 ms 1616 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6224 KB Output is correct
2 Correct 26 ms 4688 KB Output is correct
3 Correct 92 ms 7760 KB Output is correct
4 Correct 19 ms 5984 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 11344 KB Output is correct
2 Correct 96 ms 13896 KB Output is correct
3 Correct 97 ms 16976 KB Output is correct
4 Correct 90 ms 17232 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 29000 KB Output is correct
2 Correct 132 ms 23880 KB Output is correct
3 Correct 168 ms 20040 KB Output is correct
4 Correct 127 ms 18760 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 23948 KB Output is correct
2 Correct 212 ms 25928 KB Output is correct
3 Correct 231 ms 32840 KB Output is correct
4 Correct 230 ms 32024 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 39072 KB Output is correct
2 Correct 395 ms 36424 KB Output is correct
3 Correct 422 ms 36776 KB Output is correct
4 Correct 422 ms 35656 KB Output is correct
5 Correct 649 ms 32328 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 38900 KB Output is correct
2 Correct 458 ms 50192 KB Output is correct
3 Correct 502 ms 45652 KB Output is correct
4 Correct 373 ms 52040 KB Output is correct
5 Correct 839 ms 36904 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 39752 KB Output is correct
2 Correct 460 ms 42008 KB Output is correct
3 Correct 638 ms 37960 KB Output is correct
4 Correct 465 ms 39752 KB Output is correct
5 Correct 406 ms 53668 KB Output is correct
6 Correct 693 ms 38016 KB Output is correct