結果

問題 No.274 The Wall
ユーザー fiord
提出日時 2015-09-16 20:35:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 326 ms / 2,000 ms
コード長 1,974 bytes
コンパイル時間 1,952 ms
コンパイル使用メモリ 162,136 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2025-03-17 18:50:25
合計ジャッジ時間 3,855 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
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