#140214 (C++14) No.470 Inverse S+T Problem

提出ソース

結果

問題	No.470 Inverse S+T Problem
ユーザー	anta
提出日時	2016-12-21 00:14:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	11 ms / 2,000 ms
コード長	6,039 bytes
コンパイル時間	2,075 ms
コンパイル使用メモリ	187,720 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-01 22:44:05
合計ジャッジ時間	3,047 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	10 ms 6,944 KB
testcase_07	AC	11 ms 6,944 KB
testcase_08	AC	11 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,944 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	1 ms 6,944 KB
testcase_24	AC	1 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	3 ms 6,944 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	2 ms 6,940 KB

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

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

struct StaticGraph {
	typedef int Arc;
	typedef pair<int, Arc> Edge;

	struct ArcList {
		ArcList() : arcBegin(), arcEnd() {}
		ArcList(const Arc *arcBegin, const Arc *arcEnd) : arcBegin(arcBegin), arcEnd(arcEnd) {}

		const Arc *begin() const { return arcBegin; }
		const Arc *end() const { return arcEnd; }
		int size() const { return (int)(arcEnd - arcBegin); }
		bool empty() const { return arcBegin == arcEnd; }
		Arc operator[](int i) const { return arcBegin[i]; }

	private:
		const Arc * const arcBegin, *const arcEnd;
	};

	int size() const { return (int)offsets.size() - 1; }

	ArcList operator[](int i) const {
		return ArcList(arcs.data() + offsets[i], arcs.data() + offsets[i + 1]);
	}

	void init(int n, const vector<Edge> &edges) {
		int m = (int)edges.size();
		arcs.resize(m + 1);
		offsets.assign(n + 1, 0);
		for (int ei = 0; ei < m; ++ei)
			++offsets[edges[ei].first];
		for (int i = 0; i < n; ++i)
			offsets[i + 1] += offsets[i];
		for (int ei = m - 1; ei >= 0; --ei)
			arcs[--offsets[edges[ei].first]] = edges[ei].second;
	}


	vector<Arc> arcs;
	vector<int> offsets;
};

class StronglyConnectedComponents {
public:
	//typedef vector<vector<int>> Graph;
	typedef StaticGraph Graph;

	int run(const Graph &graph) {
		int n = (int)graph.size();
		stack.resize(n);
		S.resize(n);
		B.resize(n);
		I.assign(n, 0);
		int sp = 0, topS = 0, topB = 0, c = n;
		for (int start = 0; start < n; ++start) if (I[start] == 0) {
			stack[sp++] = make_pair(start, 0);
			for (; sp != 0; ) {
				int u, ei;
				tie(u, ei) = stack[--sp];
				if (ei == 0) {
					S[topS++] = u;
					B[topB++] = I[u] = topS;
				}
				if (ei != graph[u].size()) {
					stack[sp++] = make_pair(u, ei + 1);
					int v = graph[u][ei];
					if (I[v] == 0) {
						stack[sp++] = make_pair(v, 0);
					}
					else {
						while (I[v] < B[topB - 1])
							--topB;
					}
				}
				else if (I[u] == B[topB - 1]) {
					--topB, ++c;
					while (I[u] <= topS)
						I[S[--topS]] = c;
				}
			}
		}
		for (int u = 0; u < n; ++u)
			I[u] -= n + 1;
		return c - n;
	}

	int getColor(int u) const {
		return I[u];
	}

private:
	vector<pair<int, int>> stack;
	vector<int> S, B, I;
};

class TwoSatisfiability {
public:
	void init(int variables) {
		variableID.assign(variables, -1);
	}

	bool run(const vector<pair<int, int>> &clauses) {
		currentVariables.clear();
		edges.clear();
		for (const auto &clause : clauses) {
			int u = getVertex(clause.first);
			int v = getVertex(clause.second);
			edges.emplace_back(u ^ 1, v);
			edges.emplace_back(v ^ 1, u);
		}
		int n = (int)currentVariables.size();
		for (int var : currentVariables)
			variableID[var] = -1;

		graph.init(n * 2, edges);
		scc.run(graph);
		bool satisfiable = true;
		for (int i = 0; i < n; ++i)
			satisfiable &= scc.getColor(i * 2) != scc.getColor(i * 2 + 1);
		return satisfiable;
	}

	void getAssignment(vector<bool> &res) {
		int n = graph.size();
		makeCondensation();
		int S = condensation.size();
		vector<int> deg(S);
		rep(i, S) for (int j : condensation[i])
			deg[j] ++;
		vector<int> que(S, -1);
		int qt = 0;
		rep(i, S) if (deg[i] == 0)
			que[qt++] = i;
		for (int qh = 0; qh < qt; ++qh) {
			int i = que[qh];
			for (int j : condensation[i])
				if (--deg[j] == 0)
					que[qt++] = j;
		}
		vector<int> index(S, -1);
		rep(i, S)
			index[que[i]] = i;
		rep(i, (int)currentVariables.size()) {
			int ix0 = index[scc.getColor(i * 2 + 0)];
			int ix1 = index[scc.getColor(i * 2 + 1)];
			res[currentVariables[i]] = ix0 < ix1;
		}
	}

private:
	void makeCondensation() {
		int n = graph.size();
		vector<pair<int, int>> edges;
		rep(i, n) for (int j : graph[i]) if (scc.getColor(i) != scc.getColor(j))
			edges.emplace_back(scc.getColor(i), scc.getColor(j));
		int S = 0;
		rep(i, n)
			amax(S, scc.getColor(i) + 1);
		condensation.init(S, edges);
	}

	int getVertex(int lit) {
		int &id = variableID[lit >> 1];
		if (id == -1) {
			id = (int)currentVariables.size();
			currentVariables.push_back(lit >> 1);
		}
		return id << 1 | (lit & 1);
	}

	vector<int> variableID;
	vector<int> currentVariables;
	vector<pair<int, int>> edges;
	StronglyConnectedComponents::Graph graph;
	StronglyConnectedComponents scc;
	StronglyConnectedComponents::Graph condensation;
	int sccS;
};

int main() {
	TwoSatisfiability ts;
	int N;
	while (~scanf("%d", &N)) {
		vector<string> Us(N);
		rep(i, N) {
			char U[4];
			scanf("%s", U);
			Us[i] = U;
		}
		if (N > 52) {
			puts("Impossible");
			continue;
		}
		vector<pair<int, int>> clauses;
		auto addClause = [&](int i, int bi, int j, int bj) {
			clauses.emplace_back(i * 2 + (1 - bi), j * 2 + (1 - bj));
		};
		rep(i, N) reu(j, i + 1, N) {
			if (i < j) {
				if (Us[i][0] == Us[j][0] || (Us[i][1] == Us[j][1] && Us[i][2] == Us[j][2]))
					addClause(i, 0, j, 0);
				if (Us[i][2] == Us[j][2] || (Us[i][0] == Us[j][0] && Us[i][1] == Us[j][1]))
					addClause(i, 1, j, 1);
			}
			if (Us[i][0] == Us[j][2] || (Us[i][1] == Us[j][0] && Us[i][2] == Us[j][1]))
				addClause(i, 0, j, 1);
			if (Us[i][2] == Us[j][0] || (Us[i][0] == Us[j][1] && Us[i][1] == Us[j][2]))
				addClause(i, 1, j, 0);
		}
		TwoSatisfiability twoSat;
		twoSat.init(N);
		bool ok = twoSat.run(clauses);
		if (!ok) {
			puts("Impossible");
		}
		else {
			vector<bool> ans(N);
			twoSat.getAssignment(ans);
			rep(i, N) {
				if (!ans[i])
					printf("%c %c%c\n", Us[i][0], Us[i][1], Us[i][2]);
				else
					printf("%c%c %c\n", Us[i][0], Us[i][1], Us[i][2]);
			}
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード