結果
問題 | No.274 The Wall |
ユーザー |
![]() |
提出日時 | 2015-08-04 20:02:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 362 ms / 2,000 ms |
コード長 | 2,466 bytes |
コンパイル時間 | 943 ms |
コンパイル使用メモリ | 91,856 KB |
実行使用メモリ | 132,608 KB |
最終ジャッジ日時 | 2024-06-22 01:56:32 |
合計ジャッジ時間 | 2,600 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
#include <algorithm>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <functional>#include <iostream>#include <map>#include <memory>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>#include <cassert>using namespace std;#define sz size()#define pb push_back#define mp make_pair#define fi first#define se second#define all(c) (c).begin(), (c).end()#define rep(i,a,b) for(int i=(a);i<(b);++i)#define clr(a, b) memset((a), (b) ,sizeof(a))#define MOD 1000000007#define MAX_V 6000 // 制約を上げました。vector<int> graph[MAX_V];vector<int> rev_graph[MAX_V];bool visited[MAX_V];int cmp[MAX_V];vector<int> st;void ae(int from, int to){graph[from].pb(to);rev_graph[to].pb(from);}void dfs(int v){visited[v] = true;for(int i=0; i<(int)graph[v].size(); i++){int u = graph[v][i];if(!visited[u]){dfs(u);}}st.push_back(v);}void rev_dfs(int v, int cnt){visited[v] = true;for(int i=0; i<(int)rev_graph[v].size(); i++){int u = rev_graph[v][i];if(!visited[u]){rev_dfs(u, cnt);}}cmp[v] = cnt;}void scc(){memset(visited, 0, sizeof(visited));memset(cmp, 0, sizeof(cmp));st.clear();for(int i=0; i<MAX_V; i++){if(!visited[i]){dfs(i);}}memset(visited, 0, sizeof(visited));int cnt = 0;while(!st.empty()){int v = st.back();st.pop_back();if(!visited[v]){rev_dfs(v, cnt++);}}}int n,m;int rev(int p){return m-p-1;}int main(){cin>>n>>m;if(n>3000)return -1;if(m>4000)return -1;vector<int> vl;vector<int> vr;rep(i,0,n){int l,r;cin>>l>>r;if(l>=m)return -1;if(r>=m)return -1;vl.pb(l);vr.pb(r);}rep(i,0,n){rep(j,i+1,n){if(vl[i]<=vr[j]&&vl[j]<=vr[i]){ae(j,3000+i);ae(i,3000+j);}if(rev(vr[i])<=vr[j]&&vl[j]<=rev(vl[i])){ae(j,i);ae(3000+i,3000+j);}if(vl[i]<=rev(vl[j])&&rev(vr[j])<=vr[i]){ae(3000+j,3000+i);ae(i,j);}if(rev(vr[i])<=rev(vl[j])&&rev(vr[j])<=rev(vl[i])){ae(3000+i,j);ae(3000+j,i);}}}scc();rep(i,0,n){if(cmp[i]==cmp[3000+i]){cout << "NO" << endl;return 0;}}cout << "YES" << endl;return 0;}