結果

問題 No.483 マッチ並べ
ユーザー vjudge1
提出日時 2025-01-27 21:31:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 2,767 bytes
コンパイル時間 1,737 ms
コンパイル使用メモリ 169,484 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-27 21:32:10
合計ジャッジ時間 3,357 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 110;
const int V = 4 * N;
const int E = 2e5 + 10;
struct Graph
{
    struct Edge
    {
        int to, next;
    } e[E];
    int head[V], idx;
    inline void add(int u, int v)
    {
        e[++idx] = {v, head[u]};
        head[u] = idx;
    }
} g;
ll n;
struct Point
{
    ll x1, y1, id1;
    ll x2, y2, id2;
} a[N];
ll idx;
vector<ll> vec[N][N];
stack<int> s;
int timer, dfn[V], low[V], in[V];
int ble[V], scc;
inline void Tarjan(int u)
{
    dfn[u] = low[u] = ++timer;
    s.push(u), in[u] = 1;
    for (int i = g.head[u]; i; i = g.e[i].next)
    {
        int v = g.e[i].to;
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        int t;
        ++scc;
        do
        {
            t = s.top();
            s.pop();
            ble[t] = scc;
            in[t] = 0;
        } while (t != u);
    }
}
inline void clean()
{
    idx = g.idx = 0;
    for (int i = 1; i <= 4 * n; i++)
        g.head[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            vec[i][j].clear();
    timer = scc = 0;
    for (int i = 1; i <= 4 * n; i++)
        dfn[i] = low[i] = in[i] = ble[i] = 0;
}
inline void solve()
{
    clean();
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        a[i].id1 = ++idx, a[i].id2 = ++idx;
        vec[a[i].x1][a[i].y1].push_back(a[i].id1);
        vec[a[i].x2][a[i].y2].push_back(a[i].id2);
    }
    for (ll i = 1; i <= 100; i++)
        for (ll j = 1; j <= 100; j++)
            if (vec[i][j].size() > 4)
            {
                cout << "NO" << endl;
                return;
            }
    for (ll i = 1; i <= n; i++)
    {
        g.add(a[i].id1, a[i].id2 + 2 * n);
        g.add(a[i].id2 + 2 * n, a[i].id1);
        g.add(a[i].id2, a[i].id1 + 2 * n);
        g.add(a[i].id1 + 2 * n, a[i].id2);
    }
    for (ll i = 1; i <= 100; i++)
        for (ll j = 1; j <= 100; j++)
            for (auto id1 : vec[i][j])
                for (auto id2 : vec[i][j])
                    if (id1 != id2)
                        g.add(id1 + 2 * n, id2);
    for (int i = 1; i <= 4 * n; i++)
        if (!dfn[i])
            Tarjan(i);
    for (ll i = 1; i <= 2 * n; i++)
        if (ble[i] == ble[i + 2 * n])
        {
            cout << "NO" << endl;
            return;
        }
    cout << "YES" << endl;
}
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll T = 1;
    while (T--)
        solve();
    return 0;
}
0