Submission #1020490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020490		BuzzyBeez	Untitled (POI11_rot)	C++17	0 / 100	129 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 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, timer = 1, id = 1;
void Input(){
	int x; cin >> x;
	if(x!=0) {_list[id].insert(x); return;}
	int t = id;
	adj[t].push_back(id+1);
	id++ ; Input();
	adj[t].push_back(id+1);
	id++ ; Input();
}

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 << endl;
		if (!adj[v].empty()) 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; Input();
	DFS(1, 0); cout << inv[1];
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 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