oj.uz

Submission #1020497

# Submission time Handle Problem Language Result Execution time Memory
1020497 2024-07-12T05:56:48 Z BuzzyBeez Tree Rotations (POI11_rot) C++17
45 / 100
 1000 ms 65536 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

vector<int> adj[400008];
ordered_set _list[400008];
long long inv[400008];

void add_edge(int u, int v) {adj[u].push_back(v);}

int n, tmp, timer = 1, id = 1;
void Input(){
	int x; cin >> x;
	if(x!=0) {_list[id].insert(x); return;}
	int t = id;
	adj[t].push_back(id+1);
	id++ ; Input();
	adj[t].push_back(id+1);
	id++ ; Input();
}

int opt1, opt2;
void DFS(int u, int p) {
	vector<int> C;
	for (int v : adj[u]) if (v != p) {
		// cout << u << " -> " << v << endl;
		if (!adj[v].empty()) DFS(v, u); 
		inv[u] += inv[v]; C.push_back(v);
	}
	opt1 = opt2 = 0; 
	if (_list[C[0]].size() < _list[C[1]].size()) swap(C[0], C[1]);
	tmp = _list[C[1]].size();
	for (int v : _list[C[0]]) {
		tmp = _list[C[1]].order_of_key(v);
		opt1 += tmp; opt2 += _list[C[1]].size() - tmp;
	}
	inv[u] += min(opt1, opt2);
	for (int v : adj[u]) if (v != p) {
		if (_list[u].size() < _list[v].size()) _list[u].swap(_list[v]);
		for (int item : _list[v]) _list[u].insert(item);
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n; Input();
	DFS(1, 0); cout << inv[1];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41040 KB Output is correct
2 Correct 26 ms 41048 KB Output is correct
3 Correct 26 ms 41048 KB Output is correct
4 Correct 26 ms 41056 KB Output is correct
5 Correct 27 ms 41048 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41048 KB Output is correct
2 Correct 26 ms 41080 KB Output is correct
3 Correct 27 ms 41052 KB Output is correct
4 Correct 36 ms 41044 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41304 KB Output is correct
2 Correct 27 ms 41308 KB Output is correct
3 Correct 29 ms 41300 KB Output is correct
4 Correct 28 ms 41172 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 42220 KB Output is correct
2 Correct 43 ms 42072 KB Output is correct
3 Correct 62 ms 42056 KB Output is correct
4 Correct 65 ms 42324 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 44112 KB Output is correct
2 Correct 48 ms 44880 KB Output is correct
3 Correct 80 ms 53584 KB Output is correct
4 Correct 209 ms 44996 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 59204 KB Output is correct
2 Execution timed out 1053 ms 48952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 61780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 64352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 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 Execution timed out 1078 ms 60756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 61516 KB Time limit exceeded
2 Halted 0 ms 0 KB -