POJ 1182 食物链

蟻本のUnion-Findのやつ。
cin,coutをつかってたらTLEした。
(ios::sync_with_stdio(false);しても)

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                                                  it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))
#define eq ==

class UnionFind{
public:
    vector<int> par; // 親
    vector<int> rank; // 木の深さ
    UnionFind(int n){
        par = vector<int>(n);
        rep(i,n) par[i] = i;
        rank = vector<int>(n);
    }
    // 親を探す
    int root(int x){
        if(par[x] == x){
            return x;
        }else{
            // 縮約?
            return par[x] = root(par[x]);
        }
    }
    // x,yの含まれる集合を併合
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x==y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return root(x) == root(y);
    }
};

int main(){
    int N,K;
    scanf("%d %d",&N,&K);
    UnionFind uf(3*N);
    int ret = 0;
    for(int index=0;index<K;index++){
        int t,x,y;
        scanf("%d %d %d",&t,&x,&y);
        x--;y--;
        if(x < 0 or N <= x or y < 0 or N <= y){
            ret++;
            continue;
        }
        if(t==1){
            if(uf.same(x,y+N) or uf.same(x,y+2*N)){
                ret++;
            }else{
                uf.unite(x,y);
                uf.unite(x+N,y+N);
                uf.unite(x+2*N,y+2*N);
            }
        }else{
            if(uf.same(x,y) or uf.same(x,y+2*N)){
                ret++;
            }else{
                uf.unite(x,y+N);
                uf.unite(x+N,y+2*N);
                uf.unite(x+2*N,y);
            }
        }
    }
    printf("%d\n",ret);

    return 0;
}