oj.uz

Submission #584606

# Submission time Handle Problem Language Result Execution time Memory
584606 2022-06-27T15:54:55 Z Drew_ Type Printer (IOI08_printer) C++17
100 / 100
 152 ms 57452 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);

int n;
static int ctr = 0;

inline void out(char c)
{
	if (ctr < n)
		cout << c << '\n';
	ctr += c == 'P';
}

struct Trie
{
	bool is_word = false, lst = false;
	// Trie* to[26] = {};
	map<char, Trie*> to;

	Trie() {}
};

int main()
{
	fastio;

	cin >> n;

	string best = "";
	cin >> best;

	int sum = 0;
	Trie* root = new Trie();
	for (int i = 1; i < n; ++i)
	{
		string s; cin >> s;
		if (s.size() > best.size())
			swap(s, best);

		Trie* cur = root;
		for (char &c : s)
		{
			if (!(cur -> to.count(c)))
				sum++, cur -> to[c] = new Trie();
			cur = cur -> to[c];
		}
		cur -> is_word = true;
	}

	Trie* cur = root;
	for (char &c : best)
	{
		if (!(cur -> to.count(c)))
			sum++, cur -> to[c] = new Trie();
		cur = cur -> to[c];
		cur -> lst = true;
	}
	cur -> is_word = true;

	const auto dfs = [&](const auto &self, Trie* node) -> void
	{
		if (node -> is_word)
		{
			out('P');
			node -> is_word = false;
		}

		char pend = 0;
		for (const auto &[x, y] : node -> to)
		{
			if (y -> lst)
			{
				pend = x;
				continue;
			}
			out(x);
			self(self, y);
		}

		if (pend)
		{
			out(pend);
			self(self, node -> to[pend]);
		}

		out('-');
	};

	cout << 2 * sum + n - (int)best.size() << '\n';
	dfs(dfs, root);

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 3 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3564 KB Output is correct
2 Correct 14 ms 7240 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8612 KB Output is correct
2 Correct 10 ms 2132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21180 KB Output is correct
2 Correct 89 ms 48332 KB Output is correct
3 Correct 52 ms 24980 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16552 KB Output is correct
2 Correct 152 ms 57452 KB Output is correct
3 Correct 76 ms 28400 KB Output is correct
4 Correct 82 ms 54236 KB Output is correct