Submission #995639

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

const int MX = 120000;

int n;
int a[MX];
int b[MX];
vector<int> go[MX];

set<pair<int, int> > ss;
set<pair<int, int> > sst;
set<pair<int, int> > ss2;
set<pair<int, int> > ss2t;

vector<pair<int, int> > ed;
vector<int> vv;
map<pair<int, int>, int> mm;

void ex() {
	if (n != 3)
		assert(false);
	cout << -1 << "\n";
	exit(0);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i] >> b[i];
	if (a[0] != 0 || b[1] != 0)
		ex();
	for (int i = 0; i < n; ++i) {
		go[a[i]].push_back(i);
	}
	if ((int)go[0].size() != 1)
		ex();
	ss.insert(make_pair(b[0], 0));
	ss2.insert(make_pair(b[0], 0));
	for (int i = 0; i < n; ++i)
		mm[make_pair(a[i], b[i])] = 1;
	for (int i = 1; i < n; ++i) {
		sst.clear();
		ss2t.clear();
		for (int j: go[i]) {
			auto it = ss.lower_bound(make_pair(b[j] + 1, 0));
			ss2t.insert(make_pair(b[j], j));
			if (it != ss.end() && it->first == b[j] + 1) {
				ed.push_back(make_pair(j, it->second));
				ss.erase(it);
				sst.insert(make_pair(b[j], j));
			}
			else {
				auto it = ss2.lower_bound(make_pair(b[j] - 1, 0));
				if (it != ss2.end() && it->second <= b[j] + 1) {
					if (it->second != b[j] - 1)
						sst.insert(make_pair(b[j], j));
					ed.push_back(make_pair(j, it->second));
				}
				else {
					ex();
				}
			}
		}
		for (auto j: ss)
			vv.push_back(j.second);
		swap(ss, sst);
		swap(ss2, ss2t);
	}
	for (int j: vv) {
		if (j == 1)
			continue;
		int fl = 0;
		for (int d = -1; d <= 1; ++d) {
			if (mm.count(make_pair(a[j] + d, b[j] - 1))) {
				fl = 1;
				ed.push_back(make_pair(mm[make_pair(a[j] + d, b[j] - 1)], j));
				break;
			}
		}
		if (!fl) {
			ex();
		}
	}
	cout << ed.size() << "\n";
	/*for (auto j: ed) {
		cout << j.first + 1 << " " << j.second + 1 << "\n";
	}*/
	return 0;
}

Submission Info

Judge Result