WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #189 Div2 B "Ping-Pong (Easy Version)"

問題

http://codeforces.com/contest/320/problem/B

あなたは区間のセットを常に持っている。あなたは2つの区間(a, b)と(c, d)において、( c < a < d )または( c < b < d )であれば、区間(a, b)から区間(b, c)へ移動する事ができる。さらに、区間I1と区間I2に移動するときに、複数回、区間を移動することが可能である。

あなたの課題は下記のような2つのタイプのクエリに答える事である。

"1 x y" (x < y)... 区間(x, y)を追加する。新たな区間の長さは
                   今までのどの区間よりも長い事が保証される。
"2 a b" (a != b)...a番目の区間からb番目の区間へ移動する事が出来るか?

全てのクエリに答えよ。なお、初めはひとつも区間を持っていない。



考えた事

区間a->bに一回でいけるかどうかのグラフを作成する。2番目のクエリはdfsで


ソースコード

bool G[110][110];
int as[110];
int bs[110];
bool chk[110];

// s->tにたどり着けるか?
bool dfs( int s, int t ){

    if( s == t ) return true;

    chk[s] = true;

    bool res = false;
    for( int to = 0; to < 100; to++ ){
        if( !G[s][to] || chk[to] ) continue;
    
        res |= dfs( to, t );
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    int m = 0;
    memset( G, false, sizeof(G) );
    for( int i = 0; i < n; i++ ){
        int op, a, b;
        cin >> op >> a >> b;

        // 区間を追加する
        if( op == 1 ){
            for( int j = 0; j < m; j++ ){
                int c = as[j];
                int d = bs[j];
                if( (c < a && a < d) || (c < b && b < d) ){
                    G[m][j] = true;
                }
                if( (a < c && c < b) || (a < d && d < b) ){
                    G[j][m] = true;
                }
            }
            as[m] = a;
            bs[m] = b;
            m++;
        }

        // a->bにいけるかどうか答える
        if( op == 2 ){
            memset( chk, false, sizeof(chk) );
            if( dfs( a-1, b-1 ) ){
                cout << "YES" << endl;
            }else{
                cout << "NO" << endl;
            }
        }
    }
}