oj.uz

Submission #886755

# Submission time Handle Problem Language Result Execution time Memory
886755 2023-12-12T21:39:15 Z OAleksa Tree Rotations (POI11_rot) C++14
36 / 100
 87 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 f first
#define s second
#define int long long
const int N = 2e5 + 69;
vector<int> g[2 * N];
int n, t = 1, res[N];
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;
ordered_set st[2 * N];
void napravi(int r) {
	int x;
	cin >> x;
	if (x > 0) {
		g[x + n].push_back(r);
		g[r].push_back(x + n);
	}
	else {
		g[t].push_back(r);
		g[r].push_back(t);
		napravi(t++);
	}
	if (r > 0) {
		cin >> x;
		if (x > 0) {
			g[x + n].push_back(r);
			g[r].push_back(x + n);
		}
		else {
			g[t].push_back(r);
			g[r].push_back(t);
			napravi(t++);
		}
	}
}
void dfs(int v, int p) {
	for (auto u : g[v]) {
		if (u != p) {
			dfs(u, v);
		}
	}
	if (g[v].size() == 1)
		st[v].insert(v);
	else {
		//assert(g[v].size() == 3);
		int a = -1, b = -1;
		for (auto u : g[v]) {
			if (u == p)
				continue;
			if (a == -1)
				a = u;
			else
				b = u;
		}
		if (st[a].size() < st[b].size())
			swap(a, b);
		//a b
		int k1 = 0, k2 = 0;
		for (auto u : st[b]) {
			int x = st[a].order_of_key(u + 1);
			k1 += (int)st[a].size() - x;
		}
		//b a
		for (auto u : st[b]) {
			int x = st[a].order_of_key(u + 1);
			k2 += x;
		}
		st[v].swap(st[a]);
		for (auto u : st[b])
			st[v].insert(u);
		res[v] = res[a] + res[b] + min(k1, k2);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("snowcow.in", "r", stdin);
	//freopen("snowcow.out", "w", stdout);
  int tt = 1;
	//cin >> tt;
  while (tt--) {
  	cin >> n;
  	napravi(0);
  	dfs(1, 0);
  	cout << res[1];
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 48988 KB Output is correct
2 Correct 22 ms 48772 KB Output is correct
3 Correct 22 ms 48988 KB Output is correct
4 Correct 22 ms 48984 KB Output is correct
5 Correct 21 ms 48988 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 48988 KB Output is correct
2 Correct 22 ms 48988 KB Output is correct
3 Correct 21 ms 48848 KB Output is correct
4 Correct 22 ms 49008 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49244 KB Output is correct
2 Correct 23 ms 49304 KB Output is correct
3 Correct 24 ms 49244 KB Output is correct
4 Correct 23 ms 49232 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 50268 KB Output is correct
2 Correct 29 ms 50512 KB Output is correct
3 Correct 25 ms 50264 KB Output is correct
4 Correct 25 ms 50524 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 52824 KB Output is correct
2 Correct 44 ms 54100 KB Output is correct
3 Runtime error 82 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 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 55 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 87 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 70 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 76 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 81 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -