Mobiles

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 201010
int n;
pii minimax[N];
pii children[N];
bool star[N];

void qaq() { cout<<"-1\n"; exit(0); }
int res = 0;

void swap_at(int x) {
	//cout<<"swap at: "<<x<<"\n";
	res++;
	//swap(minimax[x].F, minimax[x].S);
	//swap(minimax[children[x].F], minimax[children[x].S]);
}

int dmin = 9999999, dmax = -9999999;

void f(int x, int d) {
	if (star[x]) {
		//cout<<"minimax["<<x<<"] = "<<d<<" "<<d<<"\n";
		dmin = min(dmin, d);
		dmax = max(dmax, d);
		minimax[x] = {d, d};
		return;
	}

	int l = children[x].F, r = children[x].S;
	int lmin = 9999999, lmax = -9999999, rmin = 9999999, rmax = -9999999;

	f(l, d+1);
	f(r, d+1);

	minimax[x].F = min(minimax[l].F, minimax[r].F);
	minimax[x].S = max(minimax[l].S, minimax[r].S);

	lmin = minimax[l].F;
	lmax = minimax[l].S;
	rmin = minimax[r].F;
	rmax = minimax[r].S;

	//cout<<"at "<<x<<" {"<<lmin<<","<<lmax<<"} {"<<rmin<<","<<rmax<<"}\n";

	bool left_diff = abs(lmin - lmax) > 0;
	bool right_diff = abs(rmin - rmax) > 0;

	if (left_diff && right_diff) {
		//cout<<"kvaak\n";
		qaq();
	}
	if (left_diff && !right_diff) {
		int rball = rmin;
		if (lmin == rball) return;
		if (lmin < rball) {
			swap_at(x);
			return;
		}
	}

	if (!left_diff && right_diff) {
		int lball = lmin;
		if (rmin < lball) return;
		if (rmin == lball) {
			swap_at(x);
			return;
		}
	}

	// 2.
	if (lmin < rmax) {
		swap_at(x);
		return;
	}
}

int main() {
	IO; cin>>n;
	int cur_id = n+1;

	FOR(x,1,n+1) {
		int l, r; cin>>l>>r;
		if (l == -1) {
			l = cur_id;
			star[l] = true;
			cur_id++;
		}
		if (r == -1) {
			r = cur_id;
			star[r] = true;
			cur_id++;
		}
		children[x] = {l, r};
	}


	f(1,0);
	if (dmax - dmin > 1) qaq();
	cout<<res<<"\n";
} 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED