Submission #995650


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
#define mp make_pair
#define pb push_back
#define N 100010
int n;
int a[N], b[N];
map<PII, set<int> > A;

void end() {
	puts ("-1");
	exit(0);
}

int path[N], L;
bool v[N];

vector<int> c[N];
// c[i] = connect with path[i] and path[i+1]
int sc[N];

int main() {
  cin >> n;
  for (int i = 0; i < n; i ++) {
  	cin >> a[i] >> b[i];
  	A[mp(a[i], b[i])].insert(i);
  }
  if (a[0] != 0 || b[1] != 0 || a[1] != b[0]) end();
  L = a[1];
  path[0] = 0;
  path[L] = 1;
  for (int i = 1; i < L; i++)
  	path[i] = -1;
  for (int i = 2; i < n; i++)
  	if (a[i] + b[i] == L) {
  		if (path[a[i]] == -1) {
  		   path[a[i]] = i;
  		   v[i] = true;
  		}
  	}
  for (int i = 1; i < L; i ++)
  	if (path[i] == -1) end();
  for (int i = 2; i < n; i ++) {
    if (a[i] == 0 || b[i] == 0) end();
    if (a[i] + b[i] < L) end();
  }
  int S = 0;
  S += L; // path
  for (int i = 2; i < n; i ++) {
    if (a[i] + b[i] == L) {
      S += 2;
    } else
    if (a[i] + b[i] == L+1) {
      S += 2;
      c[a[i]-1].pb(i);
    } else {
      if (A.find(mp(a[i]-1, b[i]-1)) != A.end()) {
        S ++;
      } else {
        end();
      }
    }
  }
  for (int i = 0; i < L; i ++) {
    sc[i] = (int) c[i].size();
  }
  for (int i = 0; i < L-1; i ++) {
    int T = min(sc[i], sc[i+1]);
    S -= T;
  }
  cout << S << endl;
  return 0;
}

Submission Info

Submission Time
Task A - Distance Pairs
User tourist
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1465 Byte
Status WA
Exec Time 156 ms
Memory 18304 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 1500
Status
AC × 2
AC × 16
WA × 17
Set Name Test Cases
sample sample-01.txt, sample-02.txt
All sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt
Case Name Status Exec Time Memory
01-01.txt AC 126 ms 17792 KB
01-02.txt AC 77 ms 8064 KB
01-03.txt AC 5 ms 2560 KB
01-04.txt AC 5 ms 2560 KB
01-05.txt WA 6 ms 2688 KB
01-06.txt WA 41 ms 5760 KB
01-07.txt WA 95 ms 8576 KB
01-08.txt WA 92 ms 8704 KB
01-09.txt WA 86 ms 8320 KB
01-10.txt WA 74 ms 8064 KB
01-11.txt WA 100 ms 8320 KB
01-12.txt WA 100 ms 8320 KB
01-13.txt WA 156 ms 17664 KB
01-14.txt WA 127 ms 18304 KB
01-15.txt AC 154 ms 17408 KB
01-16.txt WA 70 ms 8064 KB
01-17.txt WA 72 ms 8064 KB
01-18.txt AC 75 ms 8700 KB
01-19.txt WA 133 ms 17664 KB
01-20.txt WA 123 ms 15744 KB
01-21.txt WA 131 ms 16000 KB
01-22.txt WA 111 ms 12288 KB
01-23.txt AC 92 ms 8704 KB
01-24.txt AC 91 ms 8704 KB
01-25.txt AC 91 ms 8448 KB
01-26.txt AC 92 ms 8448 KB
01-27.txt AC 89 ms 8576 KB
01-28.txt AC 92 ms 8704 KB
01-29.txt WA 5 ms 2560 KB
01-30.txt AC 5 ms 2560 KB
01-31.txt AC 5 ms 2560 KB
sample-01.txt AC 5 ms 2560 KB
sample-02.txt AC 5 ms 2560 KB