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; } } } }