#603261 (C++17) No.1365 [Cherry 1st Tune] Whose Fault?

提出ソース

結果

問題	No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー	iaNTU
提出日時	2021-01-14 23:24:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,769 bytes
コンパイル時間	2,677 ms
コンパイル使用メモリ	215,376 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-09 06:42:35
合計ジャッジ時間	8,536 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	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	WA	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	RE	-
testcase_39	RE	-
testcase_40	RE	-
testcase_41	RE	-
testcase_42	RE	-
testcase_43	WA	-
testcase_44	RE	-
testcase_45	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// O(6^k * (n + m))
// Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
typedef long long int ll;
ll ABS(ll n) {return n >= 0 ? n : -n;}
constexpr int kN = int(4E3 + 10);
// constexpr int kMod = 998244353;
// constexpr int kInf = 0x3f3f3f3f
// constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;

int a[kN], b[kN], c[kN], p[kN], ans[kN], dep[kN], low[kN], scc[kN];
bitset<kN> is_big, in, went;
bitset<26> bs[kN];
vector<int> big_edge[kN], small_edge[kN], colors[kN], new_colors[kN], graph[kN];
vector<int> big, small;
stack<int> st;

int Find(int n) {return n == p[n] ? n : p[n] = Find(p[n]);}
void Merge(int l, int r) {
	l = Find(l), r = Find(r);
	p[r] = l;
	bs[l] &= bs[r];
	return ;
}

void tarjan(int cur) {
	static int t = 0, scccnt = 0;
	st.push(cur);
	low[cur] = dep[cur] = ++t;
	in[cur] = went[cur] = true;
	for (int i : graph[cur]) {
		if (!went[i]) tarjan(i);
		if (in[i]) low[cur] = min(low[cur], low[i]);
	}
	
	if (low[cur] == dep[cur]) {
		while (st.top() != cur) {
			in[st.top()] = false;
			scc[st.top()] = scccnt;
			st.pop();
		}
		// st.top() == cur
		in[st.top()] = false;
		scc[st.top()] = scccnt++;
		st.pop();
	}

	return ;
}

bool check() {
	// make all small degree 2
	bool good = true;
	queue<int> q;
	for (int i : big) for (int j : big_edge[i]) if (ans[j] == ans[i]) good = false;

	for (int i : small) new_colors[i].clear();
	for (int i : small) ans[i] = -1;

	for (int i : small) {
		for (int color : colors[i]) {
			for (int j : big_edge[i]) if (ans[j] == color) goto check_Bad;
check_Good:
			new_colors[i].PB(color);
check_Bad:
			continue;
		}

		if (int(new_colors[i].size()) == 0) good = false;
		else if (int(new_colors[i].size()) == 1) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (new_colors[cur].empty()) continue;
		
		ans[cur] = new_colors[cur][0];
		for (int i : small_edge[cur]) if (!new_colors[i].empty()) {
			vector<int> tmp;
			swap(tmp, new_colors[i]);
			for (int color : tmp) if (color != ans[cur]) new_colors[i].PB(color);

			if (int(tmp.size()) > int(new_colors[i].size())) {
				if (new_colors[i].empty()) good = false;
				else q.push(i);
			}
		}
	}
	
	// int(new_colors[i].size()) == 2

	for (int i : small) if (ans[i] == -1) {
		graph[i << 1].clear();
		graph[i << 1 | 1].clear();
	}
	
	for (int i : small) if (ans[i] == -1 && int(new_colors[i].size()) == 2) {
		for (int j : small_edge[i]) if (ans[j] == -1 && int(new_colors[j].size()) == 2) {

			for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) if (new_colors[i][x] == new_colors[j][y]) {
				graph[i << 1 | x].PB(j << 1 | (y ^ 1));
				graph[j << 1 | y].PB(i << 1 | (x ^ 1));
			}

		}
	}

	in.reset();
	went.reset();
	for (int i : small) if (ans[i] == -1) {
		if (!went[i << 1]) tarjan(i << 1);
		if (!went[i << 1 | 1]) tarjan(i << 1 | 1);
		if (scc[i << 1] == scc[i << 1 | 1]) good = false;
	}

	if (!good) return false;
	for (int i : small) if (ans[i] == -1) {
		if (scc[i << 1] < scc[i << 1 | 1]) ans[i] = new_colors[i][0];
		else ans[i] = new_colors[i][1];
	}

	return true;
}

bool dfs(int idx) {
	if (idx >= int(big.size())) return check();
	else {
		for (int color : colors[big[idx]]) {
			ans[big[idx]] = color;
			if (dfs(idx + 1)) return true;
			ans[big[idx]] = -1;
		}
		return false;
	}
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//freopen("file_name", "r", stdin);
	//freopen("file_name", "w", stdout);
	//fstream input, output;
	//input.open("file_name", ios::in);
	//output.open("file_name", ios::out);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		for (int j = 1; j <= t; j++) {
			char k;
			cin >> k;
			bs[i][k - 'a'] = true;
		}
	}

	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = 1; i <= m; i++) if (c[i] == 1) Merge(a[i], b[i]);

	for (int i = 1; i <= n; i++) if (p[i] == i && bs[i].none()) goto Fault;

	for (int i = 1; i <= n; i++) if (p[i] == i) {
		if (bs[i].count() >= 3) big.PB(i);
		else small.PB(i);
	}

	for (int i : big) is_big[i] = true;

	for (int i = 1; i <= m; i++) if (c[i] == 0) {
		int l = Find(a[i]), r = Find(b[i]);

		if (is_big[r]) big_edge[l].PB(r);
		else small_edge[l].PB(r);

		if (is_big[l]) big_edge[r].PB(l);
		else small_edge[r].PB(l);
	}

	for (int i = 1; i <= n; i++) if (p[i] == i) for (int j = 0; j < 26; j++) if (bs[i][j]) colors[i].PB(j);
	for (int i : big) ans[i] = -1;

	if (!dfs(0)) goto Fault;

	for (int i = 1; i <= n; i++) cout << char(ans[Find(i)] + 'a');
	cout << "\n";
	return 0;
Fault:
	cout << "Fault\n";
	return 0;
	//input.close();
	//output.close();
}

yukicoder

結果

テストケース

ソースコード