結果

問題 No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー iaNTUiaNTU
提出日時 2021-01-14 19:48:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,348 bytes
コンパイル時間 2,662 ms
コンパイル使用メモリ 215,040 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-09 06:42:00
合計ジャッジ時間 8,467 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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// O(3^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> 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
	queue<int> q;
	for (int i : small) new_colors[i] = colors[i];
	memset(ans, -1, sizeof(ans));

	for (int i : small) {
		if (int(new_colors[i].size()) == 0) return false;
		else if (int(new_colors[i].size()) == 1) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		
		ans[cur] = new_colors[cur][0];
		for (int i : edge[cur]) {
			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()) return 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) {
		for (int j : edge[i]) if (ans[j] == -1) {

			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]) 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 {
		vector<int> tmp;
		swap(tmp, colors[big[idx]]);
		for (int i = 0; i < int(tmp.size()); i += 2) {
			colors[big[idx]].PB(tmp[i]);
			if (i <= int(tmp.size()) - 1) colors[big[idx]].PB(tmp[i + 1]);
			if (dfs(idx + 1)) return true;
			else colors[big[idx]].clear();
		}
		swap(tmp, colors[big[idx]]);
		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) {
		small.PB(i);
		if (bs[i].count() >= 3) big.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]);
		edge[l].PB(r);
		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);

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