oj.uz

Submission #886758

# Submission time Handle Problem Language Result Execution time Memory
886758 2023-12-12T21:46:18 Z OAleksa Tree Rotations (POI11_rot) C++14
54 / 100
 162 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);
		st[b].clear();
		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 22 ms 48984 KB Output is correct
2 Correct 22 ms 48984 KB Output is correct
3 Correct 26 ms 49240 KB Output is correct
4 Correct 22 ms 48988 KB Output is correct
5 Correct 24 ms 48984 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 48988 KB Output is correct
2 Correct 25 ms 48984 KB Output is correct
3 Correct 22 ms 48988 KB Output is correct
4 Correct 28 ms 48844 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48988 KB Output is correct
2 Correct 23 ms 48988 KB Output is correct
3 Correct 28 ms 49208 KB Output is correct
4 Correct 24 ms 48984 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49992 KB Output is correct
2 Correct 28 ms 49500 KB Output is correct
3 Correct 25 ms 50012 KB Output is correct
4 Correct 26 ms 50200 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 52052 KB Output is correct
2 Correct 43 ms 50768 KB Output is correct
3 Correct 86 ms 54140 KB Output is correct
4 Correct 37 ms 52304 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 57684 KB Output is correct
2 Correct 85 ms 60320 KB Output is correct
3 Correct 101 ms 63348 KB Output is correct
4 Correct 87 ms 63572 KB Output is correct

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 162 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 92 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 77 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 79 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -