oj.uz

Submission #1115153

# Submission time Handle Problem Language Result Execution time Memory
1115153 2024-11-20T07:16:00 Z VectorLi Tree Rotations (POI11_rot) C++17
27 / 100
 52 ms 65536 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) 4E5;
 
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 51 ms 64664 KB Output is correct
2 Correct 50 ms 64816 KB Output is correct
3 Correct 48 ms 64840 KB Output is correct
4 Correct 47 ms 64808 KB Output is correct
5 Correct 49 ms 64632 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64720 KB Output is correct
2 Correct 45 ms 64840 KB Output is correct
3 Correct 43 ms 64848 KB Output is correct
4 Correct 43 ms 64840 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 64848 KB Output is correct
2 Correct 44 ms 64840 KB Output is correct
3 Correct 43 ms 64848 KB Output is correct
4 Correct 43 ms 64848 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 65496 KB Output is correct
2 Runtime error 47 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -