結果

問題 No.483 マッチ並べ
ユーザー 夜
提出日時 2021-02-15 21:10:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,575 bytes
コンパイル時間 1,421 ms
コンパイル使用メモリ 113,916 KB
実行使用メモリ 17,472 KB
最終ジャッジ日時 2024-07-23 12:52:56
合計ジャッジ時間 3,666 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int n, m;
bool bo[200020] = { false };
vector<vector<int>> vec(200020), vec1(200020);
vector<vector<int>> ans(200020); 
int ans1[200020];
void scc(){
    vector<pair<int, int>> mem_co;
    stack<int> st;
    int co = 1;
    for (int i = 0; i < n; i++) {
        if (!bo[i]) {
            st.push(i);
            bo[i] = true;
            while (!st.empty()) {
                int now = st.top();
                bool stb = false;
                for (int j = 0; j < vec[now].size(); j++) {
                    if (!bo[vec[now][j]]) {
                        bo[vec[now][j]] = true;
                        stb = true;
                        st.push(vec[now][j]);
                        break;
                    }
                }
                if (!stb) {
                    mem_co.emplace_back(make_pair(co, now));
                    co++;
                    st.pop();
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bo[i] = false;
    }
    sort(mem_co.rbegin(), mem_co.rend());
    co = 0;
    for (int i = 0; i < n; i++) {
        if (!bo[mem_co[i].second]) {
            st.push(mem_co[i].second);
            bo[mem_co[i].second] = true;
            while (!st.empty()) {
                int now = st.top();
                st.pop();
                ans[co].emplace_back(now);
                ans1[now] = co;
                for (int j = 0; j < vec1[now].size(); j++) {
                    if (!bo[vec1[now][j]]) {
                        bo[vec1[now][j]] = true;
                        st.push(vec1[now][j]);
                    }
                }
            }
            sort(ans[co].begin(), ans[co].end());
            co++;
        }
    }
}
int a[220], b[220], c[220], d[220];
int main() {
    int n1;
    cin >> n1;
    n = n1 * 2;
    for (int i = 0; i < n1; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    for (int i = 0; i < n1; i++) {
        for (int j = i + 1; j < n1; j++) {
            if (a[i] == a[j] && b[i] == b[j]) {
                vec[j].emplace_back(i + n1);
                vec1[i + n1].emplace_back(j);
                vec[i].emplace_back(j + n1);
                vec1[j + n1].emplace_back(i);
            }
            if (a[i] == c[j] && b[i] == d[j]) {
                vec[j + n1].emplace_back(i + n1);
                vec1[i + n1].emplace_back(j + n1);
                vec[i].emplace_back(j);
                vec1[j].emplace_back(i);
            }
            if (c[i] == a[j] && d[i] == b[j]) {
                vec[i + n1].emplace_back(j + n1);
                vec1[j + n1].emplace_back(i + n1);
                vec[j].emplace_back(i);
                vec1[i].emplace_back(j);
            }
            if (c[i] == c[j] && d[i] == d[j]) {
                vec[i + n1].emplace_back(j);
                vec1[j].emplace_back(i + n1);
                vec[j + n1].emplace_back(i);
                vec1[i].emplace_back(j + n1);
            }
        }
    }
    scc();
    for (int i = 0; i < n1; i++) {
        if (ans1[i] == ans1[i + n1]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0