結果

問題 No.274 The Wall
ユーザー okok
提出日時 2019-11-16 12:03:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,708 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 90,340 KB
実行使用メモリ 129,868 KB
最終ジャッジ日時 2023-10-25 03:49:20
合計ジャッジ時間 5,022 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,348 KB
testcase_02 WA -
testcase_03 AC 190 ms
98,692 KB
testcase_04 WA -
testcase_05 AC 2 ms
4,348 KB
testcase_06 WA -
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 321 ms
129,868 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 131 ms
59,416 KB
testcase_17 AC 125 ms
57,832 KB
testcase_18 AC 102 ms
46,812 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 120 ms
50,968 KB
testcase_23 AC 121 ms
51,232 KB
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void dfs1(vector<vector<pair<int,int>>> &graph, vector<int> &num, vector<int> &used, int node, int &con){
        
        if(used[node]) return ;
        
        used[node] = true;
        
        for(pair<int,int> next : graph[node]){
                dfs1(graph, num, used, next.first, con);
        }
        
        num[con++] = node;
}

void dfs2(vector<vector<pair<int,int>>> &graph, vector<int> &scc, vector<int> &used, int node, int same){
        
        if(used[node]) return ;
        
        used[node] = true;
        
        for(pair<int,int> next : graph[node]){
                dfs2(graph, scc, used, next.first, same);
        }
        
        scc[node] = same;
}

void Strongly_Connected_Components(vector<vector<pair<int,int>>> &graph, vector<int> &scc){
        vector<int>  used(graph.size()), num(graph.size());
        vector<vector<pair<int,int>>> graph2(graph.size());
        int con = 0;
        
        scc.resize(graph.size());
        
        for(int i = 0; i < graph.size(); i++){
                dfs1(graph, num, used, i, con);
        }
        
        for(int i = 0; i < graph.size(); i++){
                for(int j = 0; j < graph[i].size(); j++){
                        graph2[graph[i][j].first].push_back(make_pair(i, graph[i][j].second));
                }
        }
        
        used.clear();
        used.resize(graph.size());
        
        for(int i = (int)graph.size()-1, same = 0; i >= 0; i--){
                if(!used[num[i]]){
                        dfs2(graph2, scc, used, num[i], same);
                        same++;
                }
        }
        
}


bool two_satisfiability(int num, vector<pair<pair<bool,int>,pair<bool,int>>>& closure, vector<bool>& val){
	vector<vector<pair<int,int>>> graph(num*2);
	vector<int> scc;
	
	val.resize(num);
	
	for(int i = 0; i < closure.size(); i++){
		graph[!closure[i].first.first + closure[i].first.second*2].push_back({closure[i].second.first  + closure[i].second.second*2 ,0});
		graph[!closure[i].second.first + closure[i].second.second*2].push_back({closure[i].first.first  + closure[i].first.second*2 ,0});
	}
	
	Strongly_Connected_Components(graph, scc);
	
	for(int i = 0; i < num*2; i += 2){
		if(scc[i] == scc[i+1]){
			return false;
		} else if(scc[i] > scc[i+1]){
			val[i] = true;
		} else {
			val[i] = false;
		}
	}
	return true;
}

signed main(){
	int N, M;
	vector<pair<int,int>> in;
	vector<bool> val;
	vector<pair<pair<bool,int>,pair<bool,int>>> closure;
	
	cin>>N>>M;

	in.resize(N);

	for(int i = 0; i < N; i++){
		int L, R;
		cin>>in[i*2].first>>in[i*2].second;
	}

	for(int i = 0; i < N; i++){
		for(int j = i+1; j < N; j++){
			pair<int,int> ri{M-in[i*2].second-1, M-in[i*2].first-1}, rj{M-in[j*2].second-1, M-in[j*2].first-1};
			
			if(in[i].second - in[i].first + 1 + in[j].second - in[j].first + 1 > max(in[i].second, in[j].second) - min(in[i].first, in[j].first) + 1) {
				closure.push_back({{true,i},{true,j}});
			}
			
			if(in[i].second - in[i].first + 1 + rj.second - rj.first + 1 > max(in[i].second, rj.second) - min(in[i].first, rj.first) + 1) {
				closure.push_back({{true,i},{false,j}});
			}
			
			if(ri.second - ri.first + 1 + in[j].second - in[j].first + 1 > max(ri.second, in[j].second) - min(ri.first, in[j].first) + 1) {
				closure.push_back({{false,i},{true,j}});
			}
			
			if(ri.second - ri.first + 1 + rj.second - rj.first + 1 > max(ri.second, rj.second) - min(ri.first, rj.first) + 1) {
				closure.push_back({{false,i},{false,j}});
			}
			
		}
	}
	
	if(two_satisfiability(N, closure, val)){
		cout<<"YES"<<endl;
	} else {
		cout<<"NO"<<endl;
	}
	
	return 0;
}
0