oj.uz

Submission #1115154

# Submission time Handle Problem Language Result Execution time Memory
1115154 2024-11-20T07:17:41 Z VectorLi Tree Rotations (POI11_rot) C++17
63 / 100
 120 ms 36936 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) 1E5;
 
int n;
int e[N * 2 - 1][2];
 
int t;
ordered_set<int> s[N * 2 - 1];
 
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);
		}
	}
}
 
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 12 ms 15952 KB Output is correct
2 Correct 12 ms 16196 KB Output is correct
3 Correct 12 ms 15952 KB Output is correct
4 Correct 13 ms 15952 KB Output is correct
5 Correct 12 ms 15952 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15952 KB Output is correct
2 Correct 12 ms 15952 KB Output is correct
3 Correct 14 ms 15952 KB Output is correct
4 Correct 13 ms 15968 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16976 KB Output is correct
2 Correct 18 ms 16976 KB Output is correct
3 Correct 16 ms 16976 KB Output is correct
4 Correct 20 ms 16968 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18512 KB Output is correct
2 Correct 32 ms 19336 KB Output is correct
3 Correct 78 ms 27464 KB Output is correct
4 Correct 26 ms 19536 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 32320 KB Output is correct
2 Correct 73 ms 28488 KB Output is correct
3 Correct 79 ms 30804 KB Output is correct
4 Correct 72 ms 30280 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35144 KB Output is correct
2 Correct 106 ms 34900 KB Output is correct
3 Correct 120 ms 36936 KB Output is correct
4 Correct 90 ms 31304 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 35408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 35576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 35408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 35312 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -