分析
首先用s数组来表示这个01序列从第一个开始到第i个的奇偶性。 a b even说明s[b]和s[a-1]的奇偶性相同，否则不同。 当a b even且s[b]和s[a-1]的奇偶性不同或a b odd且s[b]和s[a-1]的奇偶性相同时为错误信息。 离散化+并查集。
代码
#include <cstdio>
#include <algorithm>
using namespace std
;
int len
,n
,p
[10001],b
[10001],f
[10001],x
[10001],y
[10001],s
[10001];
int bs(int u
){
int l
=1,r
=len
,mid
;
while (l
<=r
){
mid
=(l
+r
)>>1;
if (u
==p
[mid
]) return mid
;
if (u
>p
[mid
]) l
=mid
+1; else r
=mid
-1;}
}
int getf(int u
){
if (f
[u
]==u
) return u
;
int y
=getf(f
[u
]);
s
[u
]=(s
[f
[u
]]+s
[u
])&1;
return f
[u
]=y
;
}
void uni(int i
){
s
[f
[x
[i
]]]=(s
[x
[i
]]+b
[i
])&1;
f
[f
[x
[i
]]]=y
[i
];
}
int main(){
scanf("%*d%d",&n
);
for (int i
=1;i
<=n
;i
++){
char t
; scanf("%d%d %c",&x
[i
],&y
[i
],&t
);
if (t
=='o') b
[i
]=1; while (getchar()!='\n');
p
[(i
<<1)-1]=--x
[i
]; p
[i
<<1]=y
[i
];
}
stable_sort(p
+1,p
+1+2*n
); p
[0]=1; for (int i
=2;i
<=2*n
;i
++)
if (p
[i
]!=p
[p
[0]]) p
[++p
[0]]=p
[i
]; len
=p
[0];
for (int i
=1;i
<=len
;i
++) f
[i
]=i
;
for (int i
=1;i
<=n
;i
++){
x
[i
]=bs(x
[i
]); y
[i
]=bs(y
[i
]);
if (getf(x
[i
])==getf(y
[i
])){
if (((s
[x
[i
]]+s
[y
[i
]])&1)!=b
[i
]) {printf("%d",i
-1);return 0;}}
else uni(i
);}
printf("%d",n
);
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-2612428.html
