Submission #416369

#	Time	Username	Problem	Language	Result	Execution time	Memory
416369		model_code	Long puzzle (innopolis2021_final_D)	C++17	20 / 100	112 ms	324 KiB

Main

// Created by Nikolay Budin

#ifdef DEBUG
#  define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ff first
#define ss second
#define szof(x) ((int)x.size())
#ifndef LOCAL
#  define cerr __get_ce
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;

using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n, l;
	cin >> n >> l;

	vector<pair<pii, int>> pieces;
	for (int i = 0; i < n; ++i) {
		int a;
		string b, c;
		cin >> a >> b >> c;
		int vl, vr;
		if (b == "none") {
			vl = 0;
		} else if (b == "in") {
			vl = 1;
		} else {
			vl = 2;
		}
		if (c == "none") {
			vr = 3;
		} else if (c == "in") {
			vr = 2;
		} else {
			vr = 1;
		}
		pieces.push_back({{vl, vr}, a});
	}

	vector<int> deg_in(4), deg_out(4);
	vector<vector<int>> graph(4);
	vector<int> used(4);

	function<void(int)> dfs = [&](int v) {
		used[v] = true;
		for (int to : graph[v]) {
			if (!used[to]) {
				dfs(to);
			}
		}
	};

	int ans = 0;


	for (int mask = 0; mask < 1 << n; ++mask) {
		fill(deg_in.begin(), deg_in.end(), 0);
		fill(deg_out.begin(), deg_out.end(), 0);
		int suml = 0;
		for (int i = 0; i < n; ++i) {
			if (mask & (1 << i)) {
				deg_out[pieces[i].ff.ff]++;
				deg_in[pieces[i].ff.ss]++;
				suml += pieces[i].ss;
			}
		}

		if (suml != l || deg_out[0] != 1 || deg_in[3] != 1 || deg_in[1] != deg_out[1] || deg_in[2] != deg_out[2]) {
			continue;
		}

		for (int i = 0; i < 4; ++i) {
			graph[i].clear();
		}

		for (int i = 0; i < n; ++i) {
			if (mask & (1 << i)) {
				graph[pieces[i].ff.ff].push_back(pieces[i].ff.ss);
			}
		}

		fill(used.begin(), used.end(), 0);
		dfs(0);

		if (!used[3] || ((deg_in[1] || deg_out[1]) && !used[1]) || ((deg_in[2] || deg_out[2]) && !used[2])) {
			continue;
		}

		++ans;
	}

	cout << ans << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}

#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20