#518747 (C++17) No.274 The Wall

• 問題: No.274 The Wall
• ユーザー: fura
• 提出日時: 2020-07-26 14:58:27
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 14 ms / 2,000 ms
• コード長: 1,015 bytes
• コンパイル時間: 2,061 ms
• コンパイル使用メモリ: 208,988 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-04 02:50:11
• 合計ジャッジ時間: 3,224 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	2 ms; 4,376 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,376 KB
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	5 ms; 4,376 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	3 ms; 4,380 KB
testcase_15	AC	6 ms; 4,380 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	2 ms; 4,376 KB
testcase_18	AC	2 ms; 4,380 KB
testcase_19	AC	11 ms; 4,380 KB
testcase_20	AC	12 ms; 4,376 KB
testcase_21	AC	13 ms; 4,376 KB
testcase_22	AC	14 ms; 4,380 KB
testcase_23	AC	13 ms; 4,380 KB
testcase_24	AC	14 ms; 4,376 KB
testcase_25	AC	13 ms; 4,376 KB

ソースコード

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using graph=vector<vector<int>>;

void add_undirected_edge(graph& G,int u,int v){
	G[u].emplace_back(v);
	G[v].emplace_back(u);
}

pair<bool,vector<int>> two_coloring(const graph& G){
	int n=G.size();
	vector<int> color(n,-1);
	rep(u,n) if(color[u]==-1) {
		color[u]=0;
		queue<int> Q; Q.emplace(u);
		while(!Q.empty()){
			int v=Q.front(); Q.pop();
			for(int w:G[v]){
				if(color[w]==-1){
					color[w]=1-color[v];
					Q.emplace(w);
				}
				else if(color[w]==color[v]) return {false,vector<int>()};
			}
		}
	}
	return {true,color};
}

int main(){
	int n,m; scanf("%d%d",&n,&m);
	vector<int> l(n),r(n);
	rep(i,n) scanf("%d%d",&l[i],&r[i]);

	graph G(n);
	rep(i,n) for(int j=i+1;j<n;j++) {
		int cnt=0;
		if(l[j]<=r[i] && l[i]<=r[j]) cnt++;
		if(m-r[j]-1<=r[i] && l[i]<=m-l[j]-1) cnt++;
		if(cnt==1) add_undirected_edge(G,i,j);
		if(cnt==2) return puts("NO"),0;
	}

	puts(two_coloring(G).first?"YES":"NO");

	return 0;
}