【POJ】食物連鎖

POJの問題を解きました.

http://poj.org/problem?id=1182

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方****

・実装****

・面白さ****

問題文

N匹の動物がいます.
動物には番号がついており(1,2,…,N)です.
また、動物はA,B,Cの3種類のみとします.
この世には食物連鎖があり、ここでは以下が成り立ちます.
・AがBを食べる
・BがCを食べる
・CがAを食べる
さて、動物学を学んでるこうたくんにN匹の動物についての情報をK個聞きました.
情報は以下のような形式です.
type1：xとyは同じ種類
type2：xはyを食べる
しかしこうたくんは天然ぼけなので全て正しいことを言うわけではありません.
i個目の情報がi-1個目以下の情報と矛盾する場合とNより大きい番号の情報が与えられる場合があります.
これらの情報は無視します.
K個の情報が与えられるので何個の情報が無視されるか求めてください.
情報はtype x yの順で与えられます.

制約
1≦N≦50000
0≦K≦100000

入力
N K
type_1 x_1 y_1
.
.
.
type_K x_K y_K

出力
何個の情報が無視されるか

ヒント

・「同じ種類」「弱肉強食」の管理にUnion-Find木を使う

・種類の情報が与えられていないのでxがA,B,Cの時を同時に考える

コード

まだTime Limit Exceetedしてしまいます.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define MAX_N 50000

int par[MAX_N*3]; //oya
int myrank[MAX_N*3]; //ki no hu ka sa


////////////////
//Union-Find木//
////////////////

// n要素で初期化
void init(int n){
    FOR(i, 0, n){
        //最初は全部が根
        //par mean 親
        par[i] = i;
        myrank[i] = 0;
    }
}

//木の根を求める
int find(int x){
    //根なら根の番号を返す
    if(par[x] == x) return x;
    // 途中経過の親も根にしとく
    else return par[x] = find(par[x]);
}

//xとyの属する集合を併合
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(myrank[x] < myrank[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(myrank[x] == myrank[y]) myrank[x]++;
    }
}

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

int main(){
    int N, K;
    cin >> N >> K;
    int type, x, y;

    //Union-Find treeを初期化
    //x, x+N, x+2Nをx-A,x-B,x-Cの要素とする
    //xがA,B,Cの3パターンについて矛盾がないか調べることができる
    //食物連鎖がある動物を同じグループに入れる
    init(N * 3);

    int ans = 0;
    FOR(k, 0, K){
        cin >> type >> x >> y;
        //0からに合わせる
        x--;y--;

        //ありえない数字
        if(x<0 || x>=N || y<0 || y>=N){
            ans++;
            continue;
        }
        //弱肉強食xがyを食う
        if(type == 2){
            //xがyを食うんだからx_Aとy_Aが同じグループだとダメ
            //x_Aとy_Cが同じグループだと強弱が逆だからダメ
            if(same(x, y) || same(x, y + 2 * N)) ans++;
            //矛盾がなかったら情報を更新
            else{
                unite(x, y + N);
                unite(x + N, y + 2 * N);
                unite(x + 2 * N, y);
            }
        }
        else{
          //同じなのに違う種類だったら矛盾
          if(same(x, y + N) || same(x, y + 2 * N)) ans++;
          //矛盾がなかったら情報を更新
          else{
              unite(x, y);
              unite(x + N, y + N);
              unite(x + 2 * N, y + 2 * N);
          }
        }
    }
    cout << ans << endl;
}

コメント

種類の情報がないので難しくて解けなかった.

「食物連鎖」と「同じ種類」を表すためにUnion-Find木を用いている.