結果
問題 | No.274 The Wall |
ユーザー | sntea |
提出日時 | 2017-02-20 01:10:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,638 bytes |
コンパイル時間 | 2,481 ms |
コンパイル使用メモリ | 193,276 KB |
実行使用メモリ | 373,412 KB |
最終ジャッジ日時 | 2024-12-30 05:29:46 |
合計ジャッジ時間 | 6,215 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 931 ms
373,412 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | WA | - |
testcase_12 | AC | 16 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 6 ms
5,248 KB |
testcase_15 | AC | 13 ms
5,248 KB |
testcase_16 | AC | 587 ms
205,804 KB |
testcase_17 | AC | 516 ms
188,332 KB |
testcase_18 | AC | 539 ms
201,660 KB |
testcase_19 | AC | 23 ms
5,248 KB |
testcase_20 | AC | 26 ms
5,248 KB |
testcase_21 | AC | 26 ms
5,248 KB |
testcase_22 | AC | 28 ms
5,248 KB |
testcase_23 | AC | 29 ms
5,248 KB |
testcase_24 | AC | 29 ms
5,248 KB |
testcase_25 | AC | 27 ms
5,248 KB |
ソースコード
#ifdef LOCAL111#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#define _USE_MATH_DEFINES#include <bits/stdc++.h>const int INF = 1e9;using namespace std;template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os;}#define endl '\n'#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) FOR(i,0,n)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#ifdef LOCAL111#define DEBUG(x) cout<<#x<<": "<<(x)<<endltemplate<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}#else#define DEBUG(x) truetemplate<typename T> void dpite(T a, T b){ return; }#endif#define F first#define S second#define SNP string::npos#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}typedef long long cost_t;class Edge {public:int to = -1, from = -1, rev = -1;cost_t cost = -1;Edge(){}Edge(int x,cost_t y){to = x;cost = y;}Edge(int x, int y, cost_t z){from = x;to = y;cost = z;}Edge(int x, int y, int r, cost_t z){from = x;to = y;cost = z;rev = r;}bool operator< (const Edge& x) const {if(cost != x.cost) return cost < x.cost;return to < x.to;}bool operator> (const Edge& x) const {if(cost != x.cost) return cost > x.cost;return to > x.to;}};class Graph {private:typedef vector<Edge> Edges;//const long long int INF = (long long)1e18;vector<Edges> v;int n;public:Graph(int x){n = x;v = vector<Edges>(x);}Graph(){}Edges& operator[](int x){return v[x];}const Edges& operator[](int x) const {return v[x];}int size() const {return n;}void add_edge(int from, Edge e){v[from].push_back(e);}void add_edge(int from, int to, cost_t cost = -1, int rev = -1){add_edge(from,Edge(from,to,rev,cost));}void add_uedge(int from, int to, cost_t cost = -1){add_edge(from,to,cost);add_edge(to,from,cost);}};void vizGraph(const Graph &g, bool with_dir = false, bool with_cap = false){ofstream ofs("./out.dot");if(with_dir) ofs << "graph graph_name {" << endl;else ofs << "digraph graph_name {" << endl;for(int i = 0; i < (int)g.size(); ++i) {ofs << " " << i << '[' << endl;ofs << " " << "];" << endl << endl;}for(int i = 0; i < (int)g.size(); ++i){if (!g[i].size())continue;for(const auto &e : g[i]){if(with_dir){if(e.to > i) ofs << " " << i << " -- " << e.to ;}else ofs << " " << i << " -> " << e.to ;if (with_cap) {ofs << " [ label = " << (e.cost == INF ? "inf" : to_string(e.cost)) << "];";}if(!with_dir or e.to > i)ofs << endl;}}ofs << "}" << endl;ofs.close();system("dot -T png out.dot > sample.png");}//未検証vector<int> toposort(const Graph &g){int n = g.size();vector<int> res;res.reserve(n);vector<bool> used(n,false);function<void(int)> rec = [&](int p){if(used[p]) return;used[p] = true;for(auto&& e : g[p]) {rec(e.to);}res.push_back(p);};for(int i = 0; i < n; ++i) {if(!used[i]) rec(i);}return res;}//librarytuple<vector<int>,int> SCC(const Graph &g){int n = g.size();vector<bool> used(n,false);vector<int> cmp(g.size());Graph rg(n);for(int i = 0; i < n; ++i) {for(auto&& e : g[i]) {rg.add_edge(e.to,i,e.cost);}}vector<int> vs;vs.reserve(g.size());function<void(int)> dfs = [&](int v){used[v] = true;for(auto&& e : g[v]) {if(!used[e.to]) dfs(e.to);}vs.push_back(v);};function<void(int,int)> rdfs = [&](int v, int k){used[v] = true;cmp[v] = k;for(auto&& e : rg[v]) {if(!used[e.to]) rdfs(e.to,k);}};for(int v = 0; v < n; ++v) {if(!used[v]) dfs(v);}fill(used.begin(), used.end(), false);int k = 0;for(int i = n-1; i >= 0; --i) {if(!used[vs[i]]) rdfs(vs[i], k++);}return make_tuple(cmp,k);}Graph getSCCGraph(const Graph &g, vector<int> cmp, int k){Graph res(k);for(int p = 0; p < (int)g.size(); ++p) {for(auto&& e : g[p]) {res.add_edge(cmp[p],cmp[e.to],e.cost,e.rev);}}return res;}//liblary//Graph, toposort, scc に依存class TwoSATsolver{private:Graph g;int center;public:TwoSATsolver(int n){center = n;g = Graph(2*n+1);}int f(int x){return center+x;}void add_clause(int x, int y){g.add_edge(f(-y),f(x));g.add_edge(f(-x),f(y));}//充足不可能なら空のvectorを返すvector<bool> solve(){// vizGraph(g);vector<int> cmp;int k;tie(cmp,k) = SCC(g);Graph retg = getSCCGraph(g,cmp,k);for(int i = 1; i <= center; ++i) {if(cmp[f(i)] == cmp[f(-i)]){return vector<bool>();}}vector<bool> res(center+1);vector<int> topo = toposort(retg);dpite(ALL(topo));vector<int> rtopo(k);for(int i = 0; i < k; ++i) {rtopo[topo[i]] = i;}for(int i = 1; i <= center; ++i) {int cmpi = cmp[f(i)];int cmpni = cmp[f(-i)];assert(rtopo[cmpi] != rtopo[cmpni]);if(rtopo[cmpi] > rtopo[cmpni]){res[i] = false;}else{res[i] = true;}}return res;}};typedef long long int LL;typedef unsigned long long ULL;typedef pair<int,int> P;void ios_init(){//cout.setf(ios::fixed);//cout.precision(12);#ifdef LOCAL111return;#endifios::sync_with_stdio(false); cin.tie(0);}int main(){ios_init();int n,m;while(cin >> n >> m) {vector<P> lr(n);REP(i,n) cin >> lr[i].F >> lr[i].S;auto rev = [&](P p) -> P{return {m-1-p.S,m-1-p.F};};auto intersect = [&](P x, P y) -> bool{return (x.F <= y.F and y.F <= x.S) or(x.F <= y.S and y.S <= x.S);};TwoSATsolver s(n);REP(i,n) REP(j,i){P r1 = lr[i];P r2 = lr[j];if(intersect(r1,r2)){DEBUG(1);s.add_clause(-(i+1),-(j+1));}if(intersect(r1,rev(r2))){DEBUG(2);s.add_clause(-(i+1),(j+1));}if(intersect(rev(r1),r2)){DEBUG(3);s.add_clause((i+1),-(j+1));}if(intersect(rev(r1),rev(r2))){DEBUG(4);s.add_clause((i+1),(j+1));}}auto ret = s.solve();dpite(ALL(ret));if(ret.size() == 0){cout << "NO" << endl;}else{cout << "YES" << endl;}}return 0;}