1149: [CTSC2007]风玲Mobiles

1149: [CTSC2007]风玲Mobiles

1149: [CTSC2007]风玲Mobiles

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 650   Solved: 349
[ Submit][ Status][ Discuss]

Description

   

Input

Output

输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike的条件。如果不可能满足，输出-1。

Sample Input

6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1

Sample Output

2

HINT

Source

[ Submit][ Status][ Discuss]



不能的情况很显然

如果深度最浅和最深的铃铛差值大于1，那就无解

因为无论怎样交换都无法改变铃铛的深度，所以如果左右交换一次仍不能符合题意，无解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int maxn = 5E5 + 10;
int n,ans,mi = maxn,ma,cnt,L[maxn],L1[maxn],L2[maxn];
bool flag,bo[maxn],f[4];vector<int> v[maxn];bool Judge(int x,int y) {return L1[x] >= L2[y];}
void Dfs(int x)
{if (bo[x]) {L1[x] = L2[x] = L[x];mi = min(mi,L[x]);ma = max(ma,L[x]);return;}L1[x] = maxn;for (int i = 0; i < v[x].size(); i++) {int to = v[x][i];L[to] = L[x] + 1;Dfs(to);L1[x] = min(L1[x],L1[to]);L2[x] = max(L2[x],L2[to]);}bool fl,fr;int lc = v[x][0],rc = v[x][1];if (Judge(lc,rc)) return;if (Judge(rc,lc)) {++ans; return;}flag = 1; 
}int main()
{#ifdef DMCfreopen("DMC.txt","r",stdin);#endifcin >> n; cnt = n;for (int i = 1; i <= n; i++) {int x;scanf("%d",&x);if (x == -1) x = ++cnt,bo[x] = 1;v[i].push_back(x);scanf("%d",&x);if (x == -1) x = ++cnt,bo[x] = 1;v[i].push_back(x);}L[1] = 1; Dfs(1);if (ma - mi > 1) {cout << -1;return 0;}if (flag) cout << -1;else cout << ans;return 0;
}