結果

問題 No.274 The Wall
ユーザー fiordfiord
提出日時 2015-09-16 20:35:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 330 ms / 2,000 ms
コード長 1,974 bytes
コンパイル時間 1,495 ms
コンパイル使用メモリ 165,352 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2024-06-22 02:06:36
合計ジャッジ時間 3,073 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 118 ms
68,864 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 330 ms
132,480 KB
testcase_12 AC 9 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 4 ms
6,940 KB
testcase_15 AC 9 ms
6,940 KB
testcase_16 AC 83 ms
39,552 KB
testcase_17 AC 76 ms
38,016 KB
testcase_18 AC 85 ms
40,704 KB
testcase_19 AC 16 ms
6,944 KB
testcase_20 AC 17 ms
6,940 KB
testcase_21 AC 18 ms
6,944 KB
testcase_22 AC 18 ms
6,944 KB
testcase_23 AC 18 ms
6,940 KB
testcase_24 AC 18 ms
6,940 KB
testcase_25 AC 20 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:48:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         scanf("%d %d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:50:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         for(int i=0;i<n;i++)    scanf("%d %d",&l[i],&r[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

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