結果

問題 No.483 マッチ並べ
コンテスト
ユーザー TangentDay
提出日時 2017-02-11 00:17:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,538 bytes
コンパイル時間 1,145 ms
コンパイル使用メモリ 95,336 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 11:27:14
合計ジャッジ時間 2,740 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 29
権限があれば一括ダウンロードができます

ソースコード

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