oj.uz

Submission #886763

# Submission time Handle Problem Language Result Execution time Memory
886763 2023-12-12T22:06:57 Z OAleksa Tree Rotations (POI11_rot) C++14
54 / 100
 210 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 + 2;
vector<int> g[2 * N];
int n, t = 1, ans;
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);
		st[b].clear();
		ans += 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 << ans;
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47400 KB Output is correct
2 Correct 22 ms 47196 KB Output is correct
3 Correct 23 ms 47196 KB Output is correct
4 Correct 24 ms 47196 KB Output is correct
5 Correct 22 ms 47192 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47192 KB Output is correct
2 Correct 22 ms 47196 KB Output is correct
3 Correct 23 ms 47196 KB Output is correct
4 Correct 23 ms 47192 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47452 KB Output is correct
2 Correct 24 ms 47452 KB Output is correct
3 Correct 24 ms 47452 KB Output is correct
4 Correct 24 ms 47484 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48384 KB Output is correct
2 Correct 28 ms 47956 KB Output is correct
3 Correct 26 ms 48468 KB Output is correct
4 Correct 26 ms 48504 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 50264 KB Output is correct
2 Correct 43 ms 49232 KB Output is correct
3 Correct 87 ms 52340 KB Output is correct
4 Correct 37 ms 50520 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 55680 KB Output is correct
2 Correct 85 ms 58420 KB Output is correct
3 Correct 112 ms 60824 KB Output is correct
4 Correct 86 ms 61012 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 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 Correct 210 ms 65536 KB Output is correct
2 Runtime error 138 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

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