Submission #2623193

---

Source Code Expand

#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define inf 1000000007
#define inf16 0x3f3f3f3f
#define INF 1000000000000000007LL
#define VI vector<int>
#define VPII vector<pair<int, int> >
#define VLL vector<ll>
#define PII pair<int, int>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
using namespace std;

const int N = 1e5+7;

int n, ans;

int A[N];
int B[N];

PII mB[N]; //maksymalne B dla danego A
PII mA[N]; //maksymalne A dla danego B

map<PII, int> takie;

VI G[N];

queue<int> Q;

int dist[3][N];

bool check()
{
	for(int i = 1; i <= 2; ++i)
	{
		for(int v = 1; v <= n; ++v)
		{
			dist[i][v] = inf;
		}

		dist[i][i] = 0;
		Q.push(i);

		while(!Q.empty())
		{
			int v = Q.front();
			Q.pop();

			for(auto it:G[v])
			{
				if(dist[i][it]>dist[i][v]+1)
				{
					dist[i][it] = dist[i][v]+1;
					Q.push(it);
				}
			}
		}
	}

	for(int i = 1; i <= n; ++i)
	{
		if(A[i]!=dist[1][i])
			return 0;

		if(B[i]!=dist[2][i])
			return 0;
	}

	return 1;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i <= n; ++i)
	{
		cin >> A[i] >> B[i];
		takie[{A[i], B[i]}] = i;
		mB[A[i]] = max(mB[A[i]], mp(B[i], i));
		mA[B[i]] = max(mA[B[i]], mp(A[i], i));
	}

	if(A[2]!=B[1] || A[1] || B[2])
	{
		cout << -1 << endl;
		return 0;
	}

	if(A[2]==1)
	{
		G[1].pb(2);
		G[2].pb(1);
		++ans;
	}

	for(int i = 3; i <= n; ++i)
	{
		if(takie.find({A[i]-1, B[i]-1})!=takie.end())
		{
			G[i].pb(takie[{A[i]-1, B[i]-1}]);
			G[takie[{A[i]-1, B[i]-1}]].pb(i);
			++ans;
		}
		else
		{
			if(mB[A[i]-1].st>B[i]-1 && mA[B[i]-1].st>A[i]-1)
			{
				G[i].pb(mB[A[i]-1].nd);
				G[i].pb(mA[B[i]-1].nd);
				G[mB[A[i]-1].nd].pb(i);
				G[mA[B[i]-1].nd].pb(i);
				ans += 2;
			}
			else
			{
				cout << -1 << endl;
				return 0;
			}
		}
	}

	if(!check())
	{
		cout << -1 << endl;
		return 0;
	}

	cout << ans << endl;
}

Submission Info

Judge Result