結果

問題 No.483 マッチ並べ
ユーザー TangentDayTangentDay
提出日時 2017-02-11 00:16:17
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,538 bytes
コンパイル時間 1,183 ms
コンパイル使用メモリ 97,044 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-09 07:53:48
合計ジャッジ時間 1,951 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

map<P, int> f, a;
VI check, x, y, d;
bool pos;
int dx[] = {-1,1,0,0}, dy[] = {0,0,1,-1};
 
void dfs(int id, int xc, int yc, int c){
    if (check[id]) return;
    check[id] = 1;
    int x1, x2, y1, y2;
    x1 = x[id], y1 = y[id];
    if (d[id] == 0) x2 = x1 + 1, y2 = y1;
    else x2 = x1, y2 = y1 + 1;
    if (x1 == xc && y1 == yc){
        a[P(x1,y1)] = c;
        a[P(x2,y2)] = c^1;
        REP(k,4){
            int xx = x1 + dx[k], yy = y1 + dy[k];
            if (xx == x2 && yy == y2) continue;
            if (f[P(xx,yy)] == 0) continue;
            int id_next = f[P(xx,yy)] - 1;
            if (check[id_next] && a[P(xx,yy)] != c) pos = false;
            dfs(id_next, xx, yy, c);
        }
        REP(k,4){
            int xx = x2 + dx[k], yy = y2 + dy[k];
            if (xx == x1 && yy == y1) continue;
            if (f[P(xx,yy)] == 0) continue;
            int id_next = f[P(xx,yy)] - 1;
            if (check[id_next] && a[P(xx,yy)] == c) pos = false;
            dfs(id_next, xx, yy, c^1);
        }
    }
    if (x2 == xc && y2 == yc){
        a[P(x2,y2)] = c;
        a[P(x1,y1)] = c^1;
        REP(k,4){
            int xx = x2 + dx[k], yy = y2 + dy[k];
            if (xx == x1 && yy == y1) continue;
            if (f[P(xx,yy)] == 0) continue;
            int id_next = f[P(xx,yy)] - 1;
            if (check[id_next] && a[P(xx,yy)] != c) pos = false;
            dfs(id_next, xx, yy, c);
        }
        REP(k,4){
            int xx = x1 + dx[k], yy = y1 + dy[k];
            if (xx == x2 && yy == y2) continue;
            if (f[P(xx,yy)] == 0) continue;
            int id_next = f[P(xx,yy)] - 1;
            if (check[id_next] && a[P(xx,yy)] == c) pos = false;
            dfs(id_next, xx, yy, c^1);
        }
    }
}
 
int main() {
    int t;
    t = 1;
    while (t--){
        int n;
        cin >> n;
        pos = true;
        f.clear();
        a.clear();
        check.clear();
        check.resize(n);
        x.resize(n);
        y.resize(n);
        d.resize(n);
        REP(i,n){
            char c;
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 > x2) swap(x1, x2);
            if (y1 > y2) swap(y1, y2);
            x[i] = x1;
            y[i] = y1;
            if (x1 < x2) c = 'x';
            else c = 'y';
            f[P(x[i], y[i])] = i+1;
            if (c == 'x') f[P(x[i]+1, y[i])] = i+1, d[i] = 0;
            else f[P(x[i], y[i]+1)] = i+1, d[i] = 1;
        }
        REP(i,n){
            if (!check[i]) dfs(i, x[i], y[i], 1);
            // REP(j,n) cout << check[j];
            // cout << endl;
        }
 
        // REP(i,4){
        //     REP(j,4){
        //         cout << f[P(i,j)];
        //     }
        //     cout << endl;
        // }
        // cout << endl;
        // REP(i,4){
        //     REP(j,4){
        //         cout << a[P(i,j)];
        //     }
        //     cout << endl;
        // }
 
        cout << (pos ? "Yes" : "No") << endl;
    }
 
    return 0;
}
0