Mobiles

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
void fail(){
  cout<<-1;
  exit(0);
}
pair<int,int> comb(pair<int,int> a,pair<int,int> b) {
  return (pair<int,int>){min(a.f,b.f),max(a.s,b.s)};
}

const int N = 101010;
vector<int> v[N];
int p[N];
pair<int,int> mm[N];
int steps;

void h(int s,int dep=1) {
  pair<int,int> c = (pair<int,int>){1e9,0};
  for(auto u:v[s]) {
    if(u==-1) {
      c = comb(c,(pair<int,int>){dep+1,dep+1});
      continue;
    }
    h(u,dep+1);
    c = comb(c,mm[u]);
  }
  mm[s] = c;
}

void h1(int s,int dep=1) {
  pair<int,int> left = (pair<int,int>){dep+1,dep+1};
  if(v[s][0] != -1) left = mm[v[s][0]];
  pair<int,int> right = (pair<int,int>){dep+1,dep+1};
  if(v[s][1] != -1) right = mm[v[s][1]];
//  cout << s << " "<<left.f << ", " <<left.s << " | " << right.f << ", "<<right.s << "\n"; 
  if(right.f>left.f || left.s < right.s){
    if(right.s<left.s || right.f<left.f) fail();
    swap(v[s][0],v[s][1]);
    steps++;
//    cout << "SWAP!\n";
  }
  for(auto u:v[s]) {
    if(u==-1) {
      continue;
    }
    h1(u,dep+1);
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  for(int i=1;i<=n;i++) {
    int a,b; cin >> a >> b;
    v[i].push_back(a);
    v[i].push_back(b);
  }
  h(1);
  for(int i=1;i<=n;i++) {
    if(p[i]) {
      if(!(p[i-1] || p[i+1]))
        fail();
    }
  }
  h1(1);
  cout << steps << "\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: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED