結果

問題 No.483 マッチ並べ
ユーザー 夜夜
提出日時 2021-02-15 21:10:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,575 bytes
コンパイル時間 1,290 ms
コンパイル使用メモリ 111,712 KB
実行使用メモリ 17,144 KB
最終ジャッジ日時 2023-09-30 19:07:53
合計ジャッジ時間 4,082 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
17,052 KB
testcase_01 AC 10 ms
17,048 KB
testcase_02 AC 11 ms
17,048 KB
testcase_03 AC 9 ms
16,780 KB
testcase_04 AC 10 ms
16,840 KB
testcase_05 AC 9 ms
16,948 KB
testcase_06 AC 10 ms
16,984 KB
testcase_07 AC 9 ms
16,936 KB
testcase_08 AC 10 ms
16,980 KB
testcase_09 AC 10 ms
16,900 KB
testcase_10 AC 10 ms
16,788 KB
testcase_11 AC 10 ms
16,796 KB
testcase_12 AC 10 ms
16,856 KB
testcase_13 AC 10 ms
16,836 KB
testcase_14 AC 10 ms
16,876 KB
testcase_15 AC 10 ms
16,904 KB
testcase_16 AC 10 ms
16,884 KB
testcase_17 AC 9 ms
17,000 KB
testcase_18 AC 10 ms
17,020 KB
testcase_19 AC 10 ms
16,828 KB
testcase_20 AC 10 ms
16,904 KB
testcase_21 AC 10 ms
17,000 KB
testcase_22 AC 9 ms
17,056 KB
testcase_23 AC 10 ms
17,000 KB
testcase_24 AC 10 ms
16,960 KB
testcase_25 AC 10 ms
17,056 KB
testcase_26 AC 9 ms
16,952 KB
testcase_27 AC 10 ms
16,856 KB
testcase_28 AC 9 ms
17,072 KB
testcase_29 AC 9 ms
17,004 KB
testcase_30 AC 10 ms
16,848 KB
testcase_31 AC 10 ms
17,004 KB
testcase_32 AC 10 ms
16,900 KB
testcase_33 AC 9 ms
16,836 KB
testcase_34 AC 10 ms
17,080 KB
testcase_35 AC 10 ms
16,984 KB
testcase_36 AC 10 ms
16,796 KB
testcase_37 AC 10 ms
17,120 KB
testcase_38 AC 10 ms
16,788 KB
testcase_39 AC 9 ms
17,060 KB
testcase_40 AC 9 ms
16,948 KB
testcase_41 AC 10 ms
16,832 KB
testcase_42 AC 10 ms
16,792 KB
testcase_43 AC 10 ms
17,004 KB
testcase_44 AC 9 ms
16,964 KB
testcase_45 AC 10 ms
16,832 KB
testcase_46 AC 9 ms
16,784 KB
testcase_47 AC 10 ms
16,900 KB
testcase_48 AC 10 ms
16,828 KB
testcase_49 AC 10 ms
17,016 KB
testcase_50 AC 9 ms
17,028 KB
testcase_51 AC 9 ms
16,828 KB
testcase_52 AC 10 ms
17,076 KB
testcase_53 AC 10 ms
16,880 KB
testcase_54 AC 10 ms
17,144 KB
testcase_55 AC 9 ms
16,828 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0