結果

問題 No.274 The Wall
ユーザー fiordfiord
提出日時 2015-09-16 20:35:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 397 ms / 2,000 ms
コード長 1,974 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 148,716 KB
実行使用メモリ 132,432 KB
最終ジャッジ日時 2023-09-04 02:07:24
合計ジャッジ時間 3,171 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 134 ms
68,816 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 397 ms
132,432 KB
testcase_12 AC 6 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 4 ms
4,376 KB
testcase_15 AC 8 ms
4,380 KB
testcase_16 AC 94 ms
39,340 KB
testcase_17 AC 86 ms
37,932 KB
testcase_18 AC 93 ms
40,552 KB
testcase_19 AC 15 ms
4,376 KB
testcase_20 AC 16 ms
4,376 KB
testcase_21 AC 17 ms
4,380 KB
testcase_22 AC 17 ms
4,380 KB
testcase_23 AC 17 ms
4,380 KB
testcase_24 AC 17 ms
4,380 KB
testcase_25 AC 17 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> node[4010],rnode[4010];
int color[4010];
bool visited[4010];
int cnt=0;
vector<int> start;
bool cross(int a1,int a2,int b1,int b2){
	if(a1<=b1&&b1<=a2)	return true;
	if(a1<=b2&&b2<=a2)	return true;
	if(a1<=b1&&b2<=a2)	return true;
	if(b1<=a1&&a2<=b2)	return true;
	return false;
}
void dfs1(int now){
	visited[now]=true;
	for(int i=0;i<(int)node[now].size();i++){
		int next=node[now][i];
		if(!visited[next]){
			dfs1(next);
		}
	}
	start.push_back(now);
}
void rdfs(int now,int group){
	visited[now]=true;
	for(int i=0;i<(int)rnode[now].size();i++){
		int next=rnode[now][i];
		if(!visited[next])	rdfs(next,group);
	}
	color[now]=group;
}
void scc(){
	for(int i=0;i<4010;i++)	visited[i]=false;
	start.clear();
	for(int i=0;i<2*n;i++){
		if(!visited[i])	dfs1(i);
	}
	for(int i=0;i<4010;i++)	visited[i]=false,color[i]=0;
	int cnt=1;
	for(int i=(int)start.size()-1;i>=0;i--){
		if(!visited[start[i]])	rdfs(start[i],cnt++);
	}
}
	
int main(){
	scanf("%d %d",&n,&m);
	int l[n],r[n];
	for(int i=0;i<n;i++)	scanf("%d %d",&l[i],&r[i]);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(l[i]<=r[j]&&l[j]<=r[i]){
				node[2*i].push_back(2*j+1);
				rnode[2*j+1].push_back(2*i);
				node[2*j].push_back(2*i+1);
				rnode[2*i+1].push_back(2*j);
			}
			if(m-r[i]-1<=r[j]&&l[j]<=m-l[i]-1){
				node[2*i+1].push_back(2*j+1);
				rnode[2*j+1].push_back(2*i+1);
				node[2*j].push_back(2*i);
				rnode[2*i].push_back(2*j);
			}
			if(l[i]<=m-l[j]-1&&m-r[j]-1<=r[i]){
				node[2*i].push_back(2*j);
				rnode[2*j].push_back(2*i);
				node[2*j+1].push_back(2*i+1);
				rnode[2*i+1].push_back(2*j+1);
			}
			if(-r[i]<=-l[j]&&-r[j]<=-l[i]){
				node[2*i+1].push_back(2*j);
				rnode[2*j].push_back(2*i+1);
				node[2*j+1].push_back(2*i);
				rnode[2*i].push_back(2*j+1);
			}
		}
	}
	scc();
	for(int i=0;i<n;i++){
		if(color[2*i]==color[2*i+1]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0;
}
0