結果

問題 No.1365 [Cherry 1st Tune] Whose Fault?
コンテスト
ユーザー iaNTU
提出日時 2021-01-14 17:55:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,075 bytes
コンパイル時間 3,392 ms
コンパイル使用メモリ 206,588 KB
最終ジャッジ日時 2025-01-17 17:51:30
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 26 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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
	queue<int> q;
	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) {
			//cout << i << " have no color\n";
			//cout << "Bad big\n";
			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 : small_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()) {
					//cout << "Bad Small\n";
					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 : small_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]) {
			//cout << "Bad Scc\n";
			return false;
		}
	}
	//for (int i : small) if (ans[i] == -1) {
	//	printf("scc[%d] = %d, scc[%d] = %d\n", i << 1, scc[i << 1], i << 1 | 1, scc[i << 1 | 1]);
	//}

	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]]) {
			for (int i : big_edge[big[idx]]) if (ans[i] == color) goto Bad;
Good:
			ans[big[idx]] = color;
			if (dfs(idx + 1)) return true;
Bad:
			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()) {
		//cout << "No Color\n";
		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;
	
	//ans[Find(592)] = 'g' - 'a';
	//ans[Find(712)] = 'g' - 'a';
	//ans[Find(821)] = 'i' - 'a';
	//ans[Find(837)] = 'd' - 'a';
	//ans[Find(935)] = 'q' - 'a';
	//if (!check()) 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