CSES - APIO 2007 - Results
Submission details
Task:Mobiles
Sender:Yytsi
Submission time:2019-03-07 18:12:51 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.03 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.02 sdetails
#60.01 sdetails
#70.02 sdetails
#8ACCEPTED0.02 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.02 sdetails
#11ACCEPTED0.02 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.02 sdetails
#14ACCEPTED0.03 sdetails
#15ACCEPTED0.02 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.02 sdetails
#18ACCEPTED0.01 sdetails
#19ACCEPTED0.02 sdetails
#20ACCEPTED0.03 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.04 sdetails
#23ACCEPTED0.02 sdetails
#24ACCEPTED0.03 sdetails
#25ACCEPTED0.05 sdetails
#26ACCEPTED0.02 sdetails
#270.01 sdetails
#28ACCEPTED0.02 sdetails
#29ACCEPTED0.03 sdetails
#300.01 sdetails
#310.03 sdetails
#32ACCEPTED0.03 sdetails
#330.05 sdetails
#34ACCEPTED0.04 sdetails
#350.05 sdetails
#360.04 sdetails
#37ACCEPTED0.04 sdetails
#38ACCEPTED0.05 sdetails
#390.04 sdetails
#400.05 sdetails
#410.04 sdetails
#420.05 sdetails

Code

#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) {
			qaq();
		}
	}

	// 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 details

Test 1

Verdict: ACCEPTED

input
1
-1 -1

correct output
0

user output
0

Test 2

Verdict: ACCEPTED

input
2
2 -1
-1 -1

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
2
-1 2
-1 -1

correct output
1

user output
1

Test 4

Verdict: ACCEPTED

input
4
2 3
4 -1
-1 -1
-1 -1

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

input
4
2 3
-1 4
-1 -1
-1 -1

correct output
1

user output
1

Test 6

Verdict:

input
4
2 3
-1 -1
4 -1
-1 -1

correct output
1

user output
-1

Test 7

Verdict:

input
4
2 3
-1 -1
-1 4
-1 -1

correct output
2

user output
-1

Test 8

Verdict: ACCEPTED

input
5
2 3
4 5
-1 -1
-1 -1
...

correct output
0

user output
0

Test 9

Verdict: ACCEPTED

input
5
2 3
4 -1
5 -1
-1 -1
...

correct output
-1

user output
-1

Test 10

Verdict: ACCEPTED

input
5
2 3
4 -1
-1 5
-1 -1
...

correct output
-1

user output
-1

Test 11

Verdict: ACCEPTED

input
5
2 3
-1 4
5 -1
-1 -1
...

correct output
-1

user output
-1

Test 12

Verdict: ACCEPTED

input
5
2 3
-1 4
-1 5
-1 -1
...

correct output
-1

user output
-1

Test 13

Verdict: ACCEPTED

input
5
2 3
-1 -1
4 5
-1 -1
...

correct output
1

user output
1

Test 14

Verdict: ACCEPTED

input
6
2 3
4 5
6 -1
-1 -1
...

correct output
0

user output
0

Test 15

Verdict: ACCEPTED

input
6
2 3
4 5
-1 6
-1 -1
...

correct output
1

user output
1

Test 16

Verdict: ACCEPTED

input
6
2 3
4 -1
5 6
-1 -1
...

correct output
1

user output
1

Test 17

Verdict: ACCEPTED

input
6
2 3
-1 4
5 6
-1 -1
...

correct output
2

user output
2

Test 18

Verdict: ACCEPTED

input
19
2 3
6 5
4 7
-1 -1
...

correct output
-1

user output
-1

Test 19

Verdict: ACCEPTED

input
9
3 2
4 5
-1 -1
6 9
...

correct output
-1

user output
-1

Test 20

Verdict: ACCEPTED

input
4
-1 2
3 4
-1 -1
-1 -1

correct output
-1

user output
-1

Test 21

Verdict: ACCEPTED

input
12
3 2
4 5
-1 6
7 9
...

correct output
-1

user output
-1

Test 22

Verdict: ACCEPTED

input
10
3 2
7 5
4 6
8 10
...

correct output
-1

user output
-1

Test 23

Verdict: ACCEPTED

input
1000
2 -1
-1 3
4 -1
5 -1
...

correct output
-1

user output
-1

Test 24

Verdict: ACCEPTED

input
10000
2 -1
-1 3
4 -1
5 -1
...

correct output
-1

user output
-1

Test 25

Verdict: ACCEPTED

input
100000
2 -1
-1 3
4 -1
5 -1
...

correct output
-1

user output
-1

Test 26

Verdict: ACCEPTED

input
10
2 3
6 5
7 4
-1 -1
...

correct output
2

user output
2

Test 27

Verdict:

input
18
2 3
7 6
5 4
11 9
...

correct output
3

user output
-1

Test 28

Verdict: ACCEPTED

input
13
3 2
4 5
7 6
-1 -1
...

correct output
-1

user output
-1

Test 29

Verdict: ACCEPTED

input
660
3 2
5 6
7 4
10 8
...

correct output
-1

user output
-1

Test 30

Verdict:

input
1250
2 3
6 7
5 4
10 14
...

correct output
7

user output
-1

Test 31

Verdict:

input
5000
2 3
6 7
5 4
11 14
...

correct output
4

user output
-1

Test 32

Verdict: ACCEPTED

input
32767
2 3
5 4
7 6
13 14
...

correct output
0

user output
0

Test 33

Verdict:

input
100000
2 3
5 7
4 6
15 14
...

correct output
7

user output
-1

Test 34

Verdict: ACCEPTED

input
98348
3 2
7 5
6 4
10 8
...

correct output
-1

user output
-1

Test 35

Verdict:

input
100000
2 3
5 7
4 6
15 14
...

correct output
7

user output
-1

Test 36

Verdict:

input
99999
3 2
7 5
6 4
10 8
...

correct output
5

user output
-1

Test 37

Verdict: ACCEPTED

input
98348
3 2
7 5
6 4
10 8
...

correct output
-1

user output
-1

Test 38

Verdict: ACCEPTED

input
98303
3 2
5 4
7 6
9 8
...

correct output
1

user output
1

Test 39

Verdict:

input
98304
3 2
5 4
7 6
9 8
...

correct output
16

user output
-1

Test 40

Verdict:

input
99989
3 2
5 4
7 6
9 8
...

correct output
15

user output
-1

Test 41

Verdict:

input
99989
2 3
4 5
6 7
8 9
...

correct output
15

user output
-1

Test 42

Verdict:

input
100000
3 2
5 4
7 6
9 8
...

correct output
16

user output
-1