TIOJ 1032 . 土撥鼠 (Groundhog) ( Hash )
1032 - 土撥鼠 (Groundhog) | TIOJ INFOR Online Judge
對 ( a, b ) 加邊的時候,對 a 的 val 加上 ( a, b ) 的雜湊函數值,對 b 的 val 減下 ( a, b ) 的雜湊函數值
詢問的時候判斷是否對所有 u 的 val 相加總和為 0。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; int N, M; void init(){ cin >> N >> M; } const int MOD7122 = 1e9 + 9; int BASE7122; int hash7122( int x, int y ){ return ( 1LL * x * BASE7122 + y ) % MOD7122; } void solve(){ srand( time( NULL ) ); BASE7122 = rand() % MOD7122; vi val7122( N ); for( int i = 0; i < M; ++i ){ int op; cin >> op; if( op == 0 ){ int x, y; cin >> x >> y; if( not ( 0 <= x and x < N and 0 <= y and y < N ) ) continue; if( not ( x < y ) ) swap( x, y ); ( val7122[ x ] += hash7122( x, y ) ) %= MOD7122; ( val7122[ y ] -= hash7122( x, y ) ) %= MOD7122; } else if( op == 1 ){ int x, y; cin >> x >> y; if( not ( 0 <= x and x < N and 0 <= y and y < N ) ) continue; if( not ( x < y ) ) swap( x, y ); ( val7122[ x ] -= hash7122( x, y ) ) %= MOD7122; ( val7122[ y ] += hash7122( x, y ) ) %= MOD7122; } else{ int k; cin >> k; int sum = 0; for( int e = 0; e < k; ++e ){ int u; cin >> u; if( not ( 0 <= u and u < N ) ) continue; ( sum += val7122[ u ] ) %= MOD7122; } cout << ( sum == 0 ) << endl; } } } signed main(){ ios::sync_with_stdio( false ); init(); solve(); return 0; }