Mobiles

input/code.cpp: In function 'int main()':
input/code.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<w.size();i++) {
               ~^~~~~~~~~

#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]];
  if(right.f>left.f || left.s < right.s){
    swap(v[s][0],v[s][1]);
    steps++;
  }
  for(auto u:v[s]) {
    if(u==-1) {
      continue;
    }
    h1(u,dep+1);
  }
}
vector<int> w;
void h2(int s,int dep=1) {
  for(auto u:v[s]) {
    if(u==-1) {
      w.push_back(dep+1);
      continue;
    }
    h2(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); h2(1);
  for(int i=1;i<w.size();i++) {
    if(w[i-1]<w[i]) fail();
  }
  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: 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: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: ACCEPTED

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: 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