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

提出ソース

結果

問題	No.470 Inverse S+T Problem
ユーザー	🐬hec
提出日時	2017-05-14 13:47:14
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,383 bytes
コンパイル時間	2,340 ms
コンパイル使用メモリ	194,400 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-01 22:50:52
合計ジャッジ時間	3,244 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:
#define error(args...) {}
//{ vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) {
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ", err(++it, args...);
}


// Description: 2-SAT
// Verifyed: Many Diffrent Problem
// Required: 有向グラフに対する強連結成分

//Appropriately Changed
using edge = struct {int to;};
using G = vector<vector<edge>>;

//Appropriately Changed
void add_edge(G &graph, int from, int to) {
	error(from, to);
	graph[from].push_back({to});
}

// Description: 有向グラフに対する強連結成分
// TimeComplexity: $ \mathcal{O}(V + E) $
// Verifyed: AOJ GRL_3_C

auto strongly_connected_components(const G& graph,vector<int> &topolgy) {
	int n = graph.size(), k = 0;
	vector<int> par(n), ord(n, -1), low(n), scc(n, -1), res;
	stack<int> s;

	auto dfs = [&](int v, int p, int &k) {
		auto func = [&](int v, int p, int &k, auto func)->void{
			ord[v] = k++, low[v] = ord[v], par[v] = p, s.push(v);
			for (auto &e : graph[v]) {
				if (scc[e.to] != -1) continue;
				if (ord[e.to] == -1) {
					func(e.to, v, k, func);
					chmin(low[v], low[e.to]);
				} else
					chmin(low[v], ord[e.to]);
			}
			if (ord[v] != low[v]) return ;
			while (1) {
				int u = s.top(); s.pop();
				scc[u] = v;
				if (u == v) break;
			}
		};
		return func(v, p, k, func);
	};

	for(auto &v:topolgy) if (ord[v] == -1) dfs(v, -1, k);
	return make_tuple(scc, ord);
}

// Description: 有向グラフに対するトポロジカルソート  
// TimeComplexity: $ \mathcal{O}(V + E) $
// Verifyed: AOJ GRL_4_B
 
auto topological_sort(const G& graph){
    const int n=graph.size();
    vector<int> used(n,0),order;

    auto dfs=[&](int v){
        auto func=[&](int v,auto func)->void{
            used[v]=true;
            for(auto &e:graph[v]) if(!used[e.to]) func(e.to,func);
            order.push_back(v);
        };
        return func(v,func);
    };
    
    rep(v,n)if(!used[v]) dfs(v);
    reverse(_all(order));
    return order;
}

// x&1 == 1 True
// x&1 == 0 False
void closure_or(G &graph, int a, int b) {
	add_edge(graph, a ^ 1, b);
	add_edge(graph, b ^ 1, a);
}

auto get_variable(G &graph) {
	const int n = graph.size() / 2;
	vector<int> ret(n, 0);

	vector<int> topolgy = topological_sort(graph);
	vector<int> scc, ord;
	tie(scc, ord) = strongly_connected_components(graph,topolgy);
	rep(i, 2 * n) error(scc[i], ord[i]);

	rep(i, n) {
		if (scc[2 * i] == scc[2 * i + 1])
			ret[0] = -1;
		else {
			// F -> T というトポロジカル順序
			// 理由 F を満たすと、Tを満たすとなるためアウト
			ret[i] = (scc[2 * i + 1] >  scc[2 * i]);
		}
	}
	return ret;
}


string s[1010];

int main(void) {
	int n;
	cin >> n;

	const int limit = 52;

	if (n > limit * limit) {
		puts("Impossible");
		return 0;
	}

	rep(i, n) cin >> s[i];

	G graph(2 * n);

	// F a | bc
	// T ab | c
	rep(i, n)rep(j, i) {
		// F F
		if (s[i].substr(0, 1) == s[j].substr(0, 1) or s[i].substr(1, 2) == s[j].substr(1, 2)) {
			error(i, "F", j, "F");
			closure_or(graph, 2 * i + 1, 2 * j + 1);
		}

		// T F
		if (s[i].substr(2, 1) == s[j].substr(0, 1) or s[i].substr(0, 2) == s[j].substr(1, 2)) {
			error(i, "T", j, "F");
			closure_or(graph, 2 * i, 2 * j + 1);
		}

		// F T
		if (s[i].substr(0, 1) == s[j].substr(2, 1) or s[i].substr(1, 2) == s[j].substr(0, 2)) {
			error(i, "F", j, "T");
			closure_or(graph, 2 * i + 1, 2 * j);
		}

		// T T
		if (s[i].substr(2, 1) == s[j].substr(2, 1) or s[i].substr(0, 2) == s[j].substr(0, 2)) {
			error(i, "T", j, "T");
			closure_or(graph, 2 * i, 2 * j);
		}
	}

	vector<int> ret = get_variable(graph);

	if (ret[0] == -1) {
		puts("Impossible");
		return 0;
	}


	rep(i, n) {
		error(ret[i]);
		if (ret[i])
			cout << s[i][0] << s[i][1] << " " << s[i][2] << endl;
		else
			cout << s[i][0] << " " << s[i][1] << s[i][2] << endl;
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード