oj.uz

Submission #670599

# Submission time Handle Problem Language Result Execution time Memory
670599 2022-12-09T16:18:59 Z gokussjz Type Printer (IOI08_printer) C++17
100 / 100
 102 ms 56392 KB 
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;

const int MAX_NODES = 5e5 + 10;
const int MAX_ASCII_CODE = 26;
struct trie {
	int child[MAX_NODES][MAX_ASCII_CODE], tot, leaves[MAX_NODES];
	trie() {
		memset(child, -1, sizeof child);
		memset(leaves, 0, sizeof leaves);
		tot = 1;
	}
	void add(const string &s) {
		int node = 0;
		for (const auto &ch : s) {
			int c = ch - 'a';
			if (child[node][c] == -1) child[node][c] = tot++;
			node = child[node][c];
		}
		leaves[node]++;
	}

	bool search(const string &s) {
		int node = 0;
		for (const auto &ch : s) {
			int c = ch - 'a';
			if (child[node][c] == -1) return 0;
			node = child[node][c];
		}
		return leaves[node];
	}

	void reset() {
		memset(child, 0, sizeof(child[0]) * tot);
		memset(leaves, 0, sizeof(leaves[0]) * tot);
		tot = 1;
	}
} tr;

void solve() {
	int n;
	cin >> n;
	int mx = 0;
	string t;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		tr.add(s);
		if (mx < sz(s)) {
			mx = sz(s);
			t = s;
		}
	}

	string ans;
	function<void(int, int)> dfs = [&](int u, int hi) {
		if (tr.leaves[u]) ans += 'P';
		for (int i = 0; i < 26; i++) {
			if (tr.child[u][i] != -1) {
				if (hi != -1 && hi < sz(t) && t[hi] - 'a' == i) continue;
				ans += char(i + 'a');
				dfs(tr.child[u][i], -1);
				ans += '-';
			}
		}
		if (hi != -1 && hi < sz(t)) {
			ans += t[hi];
			dfs(tr.child[u][t[hi] - 'a'], hi + 1);
		}
	};
	dfs(0, 0);
	cout << sz(ans) << '\n';
	for (auto ch : ans) cout << ch << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 53076 KB Output is correct
2 Correct 20 ms 53156 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 53076 KB Output is correct
2 Correct 20 ms 53060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 53104 KB Output is correct
2 Correct 20 ms 53064 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 53148 KB Output is correct
2 Correct 22 ms 53152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53164 KB Output is correct
2 Correct 21 ms 53076 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53204 KB Output is correct
2 Correct 22 ms 53144 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53356 KB Output is correct
2 Correct 30 ms 53588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 53680 KB Output is correct
2 Correct 24 ms 53196 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 54180 KB Output is correct
2 Correct 83 ms 55940 KB Output is correct
3 Correct 53 ms 54840 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 53988 KB Output is correct
2 Correct 102 ms 56392 KB Output is correct
3 Correct 70 ms 55112 KB Output is correct
4 Correct 79 ms 56232 KB Output is correct