<> Parity game 【 Discretization + Joint search set 】
POJ1733,ACwing239
#include<bits/stdc++.h> using namespace std; #define int long long const int N
= 10000; struct query{ // Record the information to be queried m Sequence int l,r,ans; } v[5005]; int father[N + 5],
dis[N + 5],a[N + 5],b[N + 5]; // Record ancestors separately , Parity relationship with root node , Before discretization , After discretization int n,m,k,kk; int
find_f(int x){ // Find the ancestor node and update it dis and father array if(father[x] == x) return x; int root =
find_f(father[x]); // First traverse dis[x] ^= dis[father[x]]; // Wait for the parent node to update before updating the node information return
father[x] = root; // shorten the path } void discrete(){ // The array is obtained after discretization b sort(a + 1,a + 1 + k); b
[++kk] = a[1]; for(int i = 2;i <= k;++i) if(a[i] != a[i - 1]) b[++kk] = a[i]; }
int find_w(int x){ // Find discretization instead x Value of return lower_bound(b + 1,b + kk + 1,x) - b; }
void solve(){ for(int i = 1;i <= N;++i) // initialization father[i] = i; cin>>n>>m; int l,r,
p,q; string s; for(int i = 1;i <= m;++i){ // Input the operation and get the array before discretization a cin>>v[i].l>>v[i].r
>>s; v[i].ans = s[0] == 'e' ? 0 : 1; // There are even numbers 1 The parity of the first half and the whole segment is the same , use 0 express a[++k] = v[i].
l;a[++k] = v[i].r; } discrete(); // Discretization to get array b for(int i = 1;i <= m;++i){ l =
find_w(v[i].l) - 1;r = find_w(v[i].r); // Get the subscripts of the first half and the whole segment p = find_f(l);q = find_f(r)
; // Find the ancestral node respectively if(p == q){ // In the same set if(dis[l] ^ dis[r] != v[i].ans){
// Using the parity of two points and ancestor nodes to XOR, we can get the parity of two numbers // If not the same answer , That means you're lying cout<<i - 1; return; } } else{
// If not in the same set , Then merge and establish a relationship father[p] = q; dis[p] = dis[l] ^ dis[r] ^ v[i].ans;
//l reach r The parity of is dis[l] ^ dis[r] ^ pq Parity between // Namely :v[i].ans = dis[l] ^ dis[r] ^ pq Parity between
// obtain ：pq Parity between = v[i].ans ^ dis[l] ^ dis[r] } } cout<<m; } signed main(){ ios::
sync_with_stdio(false),cin.tie(0),cout.tie(0); // int tt; // cin>>tt; //
while(tt--) solve(); return 0; }
Technology