Submission #886755

#	Time	Username	Problem	Language	Result	Execution time	Memory
886755		OAleksa	Untitled (POI11_rot)	C++14	36 / 100	87 ms	65536 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10