結果

問題 No.274 The Wall
ユーザー monolithmonolith
提出日時 2019-03-04 11:28:30
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,725 bytes
コンパイル時間 668 ms
コンパイル使用メモリ 77,044 KB
実行使用メモリ 137,328 KB
最終ジャッジ日時 2024-06-23 13:21:51
合計ジャッジ時間 2,744 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,704 KB
testcase_01 AC 6 ms
8,704 KB
testcase_02 AC 5 ms
8,704 KB
testcase_03 AC 142 ms
74,308 KB
testcase_04 AC 5 ms
8,704 KB
testcase_05 AC 5 ms
8,644 KB
testcase_06 AC 6 ms
8,704 KB
testcase_07 AC 5 ms
8,576 KB
testcase_08 AC 6 ms
8,704 KB
testcase_09 AC 5 ms
8,808 KB
testcase_10 AC 6 ms
8,448 KB
testcase_11 AC 430 ms
137,328 KB
testcase_12 AC 25 ms
8,772 KB
testcase_13 AC 6 ms
8,768 KB
testcase_14 AC 10 ms
8,832 KB
testcase_15 AC 18 ms
8,776 KB
testcase_16 AC 126 ms
44,544 KB
testcase_17 AC 114 ms
43,844 KB
testcase_18 AC 128 ms
46,848 KB
testcase_19 AC 29 ms
8,960 KB
testcase_20 AC 33 ms
8,900 KB
testcase_21 AC 34 ms
8,704 KB
testcase_22 WA -
testcase_23 AC 35 ms
8,900 KB
testcase_24 AC 35 ms
8,960 KB
testcase_25 AC 35 ms
8,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<long long int, long long int> P;
long long int INF = 1e18;
long long int MOD = 1e9 + 7;
#define MAX_V 110000
int V;
vector<int> G[MAX_V]; //
vector<int> rG[MAX_V];//
vector<int> vs; //
bool used[MAX_V]; // 調
int cmp[MAX_V]; //
// from to
void add_edge(int from, int to){
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v){
used[v] = true;
for(int i = 0; i < G[v].size(); i++){
if(!used[G[v][i]]){
dfs(G[v][i]);
}
}
vs.push_back(v);
}
void rdfs(int v, int k){
used[v] = true;
cmp[v] = k;
for(int i = 0; i < rG[v].size(); i++){
if(!used[rG[v][i]]){
rdfs(rG[v][i], k);
}
}
}
//
int scc(){
memset(used, 0, sizeof(used));
vs.clear();
for(int v = 0; v < V; v++){
if(!used[v]){
dfs(v);
}
}
memset(used, 0, sizeof(used));
int k = 0;
for(int i = vs.size() - 1; i >= 0; i--){
if(!used[vs[i]]){
rdfs(vs[i], k++);
}
}
return k;
}
int main(){
int N, M;
cin >> N >> M;
V = N * 2;
int L[2100], R[2100];
for(int i = 0; i < N; i++){
cin >> L[i] >> R[i];
}
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){
add_edge(i, j + N);
add_edge(j, i + N);
}
swap(L[j], R[j]);
L[j] = M - L[j] - 1;
R[j] = M - R[j] - 1;
if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){
add_edge(i, j);
add_edge(j + N, i + N);
}
swap(L[j], R[j]);
L[j] = M - L[j] - 1;
R[j] = M - R[j] - 1;
swap(L[i], R[i]);
L[i] = M - L[i] - 1;
R[i] = M - R[i] - 1;
if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){
add_edge(i + N, j + N);
add_edge(j, i);
}
swap(L[j], R[j]);
L[j] = M - L[j] - 1;
R[j] = M - R[j] - 1;
if((L[i] <= L[j] && L[j] <= R[i]) || (L[i] <= R[j] && R[j] <= R[i])){
add_edge(i + N, j);
add_edge(j + N, i);
}
swap(L[i], R[i]);
L[i] = M - L[i] - 1;
R[i] = M - R[i] - 1;
swap(L[j], R[j]);
L[j] = M - L[j] - 1;
R[j] = M - R[j] - 1;
}
}
scc();
//
for(int i = 0; i < N; i++){
if(cmp[i] == cmp[i + N]){
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0