Codeforces Round #189 Div2B Ping-Pong (Easy Version)
問題
絶対値10^9までの(x,y)の組があったとき、
x'
何回も移動してI1からI2に移動できれば、I1からI2までのパスがあると言えることにします。
というわけでクエリが高々100個くらい投げられます。クエリには2種類あります。
"1 x y" -> 新たな(x,y)の組を追加します。
"2 a b" -> a番目に追加された組から、b番目に追加された組へのパスが存在するかを判定します。
解法
クエリが少ないので、2のクエリが来るたびに移動可能性のグラフ(隣接リスト)を新しく作り、
適当に探索して到達可能性を判定すればOKです。
Div2Bにしてはやや実装が面倒かなという気はしますが。
プログラム
#include<iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #define _USE_MATH_DEFINES #include <math.h> #include<string> #include<vector> #include<cmath> #include<stack> #include<queue> #include<sstream> #include<algorithm> #include<map> #include<complex> using namespace std; #define li long long int #define rep(i,to) for(int i=0;i<((int)(to));i++) #define repp(i,start,to) for(int i=(int)(start);i<((int)(to));i++) #define pb push_back #define sz(v) ((li)(v).size()) #define bgn(v) ((v).begin()) #define eend(v) ((v).end()) #define allof(v) (v).begin(), (v).end() #define dodp(v,n) memset(v,(li)n,sizeof(v)) #define bit(n) (1ll<<(li)(n)) #define mp(a,b) make_pair(a,b) #define rin rep(i,n) #define EPS 1e-10 #define ETOL 1e-8 #define MOD 1000000007 #define p2(a,b) cout<<a<<"\t"<<b<<endl #define p3(a,b,c) cout<<a<<"\t"<<b<<"\t"<<c<<endl li x[100]; li y[100]; li idx=0; bool move(li f,li t){ return ((x[t]<x[f] && x[f]<y[t]) || (x[t]<y[f] && y[f]<y[t])); } bool reach(li f, li t){ vector<li> graph[100]; rep(i,idx){ rep(j,idx){ if(i!=j && move(i,j)){ graph[i].pb(j); } } } bool visited[100]; rep(i,idx)visited[i]=false; stack<li> s; s.push(f); while(!s.empty()){ li now=s.top(); s.pop(); visited[now]=true; rep(i,sz(graph[now])){ if(graph[now][i]==t)return true; if(!visited[graph[now][i]])s.push(graph[now][i]); } } return false; } int main(){ li n; cin>>n; li tmp; li f,t; rin{ cin>>tmp; if(tmp==1){ cin>>x[idx]>>y[idx]; idx++; } else{ cin>>f>>t; if(reach(f-1,t-1))puts("YES"); else puts("NO"); } } return 0; }