oj.uz

Submission #1020445

# Submission time Handle Problem Language Result Execution time Memory
1020445 2024-07-12T04:35:44 Z BuzzyBeez Tree Rotations (POI11_rot) C++17
0 / 100
 183 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, counter;
void input(int id) {
	cin >> tmp;
	if (tmp) add_edge(id, tmp), _list[tmp].insert(tmp);
	else add_edge(id, ++counter), input(counter);
	cin >> tmp;
	if (tmp) add_edge(id, tmp), _list[tmp].insert(tmp);
	else add_edge(id, ++counter), input(counter);
}

void DFS(int u, int p) {
	int mn_L = -1, mn_R = -1; vector<int> C;
	for (int v : adj[u]) if (v != p) {
		// cout << u << " -> " << v << '\n';
		if (v > n) DFS(v, u); 
		inv[u] += inv[v]; C.push_back(v);
		if (C.size() == 1) mn_L = *_list[v].begin();
		else mn_R = *_list[v].begin();
	}
	inv[u] += min(_list[C[1]].size() - _list[C[1]].order_of_key(mn_L), _list[C[0]].size() - _list[C[0]].order_of_key(mn_R));
	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 >> tmp; counter = n + 1;
	if (tmp == 1) {cout << 0; return 0;}
	input(n + 1); DFS(n + 1, 0); cout << inv[n + 1];
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 41044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 41088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 41308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 42228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 44196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 58788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 64948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 65072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 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 152 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 157 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -