oj.uz

Submission #416369

# Submission time Handle Problem Language Result Execution time Memory
416369 2021-06-02T10:38:50 Z model_code Long puzzle (innopolis2021_final_D) C++17
20 / 100
 112 ms 324 KB 
// 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 204 KB Output is correct
2 Correct 103 ms 292 KB Output is correct
3 Correct 102 ms 204 KB Output is correct
4 Correct 102 ms 324 KB Output is correct
5 Correct 103 ms 204 KB Output is correct
6 Correct 101 ms 288 KB Output is correct
7 Correct 112 ms 204 KB Output is correct
8 Correct 104 ms 288 KB Output is correct
9 Correct 103 ms 204 KB Output is correct
10 Correct 101 ms 204 KB Output is correct
11 Correct 105 ms 292 KB Output is correct
12 Correct 107 ms 288 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 204 KB Output is correct
2 Correct 103 ms 292 KB Output is correct
3 Correct 102 ms 204 KB Output is correct
4 Correct 102 ms 324 KB Output is correct
5 Correct 103 ms 204 KB Output is correct
6 Correct 101 ms 288 KB Output is correct
7 Correct 112 ms 204 KB Output is correct
8 Correct 104 ms 288 KB Output is correct
9 Correct 103 ms 204 KB Output is correct
10 Correct 101 ms 204 KB Output is correct
11 Correct 105 ms 292 KB Output is correct
12 Correct 107 ms 288 KB Output is correct
13 Incorrect 4 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -