【POJ1733】Parity game

题面

vjudge

题解

比较简单的分类并查集

将一个查询操作看作前缀和\(s_r-s_{l-1}\)的奇偶性

将每个点拆成一奇一偶然后分别连边即可

如果一个点的奇点和偶点被连在一起了就判无解即可

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std; inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
if (ch == '-') w = -1 , ch = getchar();
while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return w * data;
}
const int MAX_N = 5005;
int M, N, l[MAX_N], r[MAX_N], X[MAX_N << 1], cnt;
int fa[MAX_N << 1];
int getf(int x) { return (x == fa[x]) ? x : (x = getf(fa[x])); }
void unite(int x, int y) { fa[getf(x)] = getf(y); }
bool same(int x, int y) { return getf(x) == getf(y); }
char ch[MAX_N][10];
int main () {
M = gi(), N = gi();
for (int i = 1; i <= N; i++) {
l[i] = gi() - 1, r[i] = gi();
X[++cnt] = l[i], X[++cnt] = r[i];
scanf("%s", ch[i]);
}
sort(&X[1], &X[cnt + 1]); cnt = unique(&X[1], &X[cnt + 1]) - X - 1;
for (int i = 1; i <= N; i++) {
l[i] = lower_bound(&X[1], &X[cnt + 1], l[i]) - X;
r[i] = lower_bound(&X[1], &X[cnt + 1], r[i]) - X;
}
for (int i = 1; i <= N * 2; i++) fa[i] = i;
for (int i = 1; i <= N; i++) {
char op = ch[i][0]; int x = l[i], y = r[i];
if (op == 'e') {
unite(x, y); unite(x + N, y + N);
if (same(x + N, x) || same(y, y + N)) return printf("%d\n", i - 1) & 0;
} else {
unite(x, y + N); unite(x + N, y);
if (same(x + N, x) || same(y, y + N)) return printf("%d\n", i - 1) & 0;
}
}
printf("%d\n", N);
return 0;
}
05-11 17:04