Submission #995936

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

int main() {
  int N; scanf("%d", &N);
  static int A[100000], B[100000];
  static pair<int, int> ABtbl[100000];
  static pair<int, int> BAtbl[100000];
  for(int i = 0; i < N; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    ABtbl[i] = make_pair(A[i], B[i]);
    BAtbl[i] = make_pair(B[i], A[i]);
  }
  if(A[0] != 0 || B[1] != 0 || A[1] == 0 || A[1] != B[0]) {
    printf("%d\n", -1);
    return 0;
  }
  sort(ABtbl, ABtbl+N);
  sort(BAtbl, BAtbl+N);
  for(int i = 0; i < N; ++i) {
    if(i != 0 &&
        lower_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]-1))
        == upper_bound(ABtbl, ABtbl+N, make_pair(A[i]-1, B[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
    if(i != 1 &&
        lower_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]-1))
        == upper_bound(BAtbl, BAtbl+N, make_pair(B[i]-1, A[i]+1))) {
      printf("%d\n", -1);
      return 0;
    }
  }
  int count = 2 * (N-1);
  for(int ii = 0; ii < N; ++ii) {
    if(ii > 0 && ABtbl[ii-1] == ABtbl[ii]) continue;
    int a = ABtbl[ii].first;
    int b = ABtbl[ii].second;
    if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))
        < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b+1))) {
      continue;
    }
    int have =
      upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
        - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
    int rem = have;
    while(true) {
      int capa = have;
      if(lower_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))
          < upper_bound(ABtbl, ABtbl+N, make_pair(a-1, b-1))) {
        // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
        //     a, b, rem, a-1, b-1);
        count -= rem;
        capa -= rem;
      }
      ++a;
      --b;
      have =
        upper_bound(ABtbl, ABtbl+N, make_pair(a, b))
          - lower_bound(ABtbl, ABtbl+N, make_pair(a, b));
      if(have == 0) break;
      // fprintf(stderr, "(%d, %d) -- %d recyclable edges to (%d, %d)\n",
      //     a-1, b+1, min(capa, have), a, b);
      count -= min(capa, have);
      rem = have - min(capa, have);
    }
  }
  printf("%d\n", count);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:7:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int N; scanf("%d", &N);
                         ^
./Main.cpp:12:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &A[i], &B[i]);
                                ^

Judge Result