oj.uz

Submission #543932

# Submission time Handle Problem Language Result Execution time Memory
543932 2022-03-31T16:01:50 Z sliviu Type Printer (IOI08_printer) C++17
100 / 100
 112 ms 99632 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	struct node {
		node* s[26] = {};
		char letter;
		int end = 0;
		node() {}
		node(char x) : letter(x) {}
	} *root = new node;
	auto insert = [&](const string& s) {
		node* cur = root;
		for (auto x : s) {
			if (!cur->s[x - 'a'])
				cur->s[x - 'a'] = new node(x);
			cur = cur->s[x - 'a'];
		}
		cur->end = 1;
	};
	vector<char> sol;
	function<void(node*)> dfs = [&](node* nod) {
		if (nod->end)
			sol.emplace_back('P');
		for (int i = 0; i < 26; ++i)
			if (nod->s[i]) {
				sol.emplace_back(nod->s[i]->letter);
				dfs(nod->s[i]);
				sol.emplace_back('-');
			}
	};
	int n;
	string maxs;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		insert(s);
		if (s.length() > maxs.length())
			maxs = s;
	}
	node* cur = root;
	for (auto x : maxs) {
		swap(cur->s[25], cur->s[x - 'a']);
		cur = cur->s[25];
	}
	dfs(root);
	while (sol.back() == '-')
		sol.pop_back();
	cout << sol.size() << '\n';
	for (auto x : sol)
		cout << x << '\n';
}

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 328 KB Output is correct

Subtask #2
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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 340 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 1108 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5972 KB Output is correct
2 Correct 14 ms 12588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14800 KB Output is correct
2 Correct 7 ms 3400 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 36564 KB Output is correct
2 Correct 99 ms 83672 KB Output is correct
3 Correct 52 ms 43168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28616 KB Output is correct
2 Correct 112 ms 99632 KB Output is correct
3 Correct 63 ms 48960 KB Output is correct
4 Correct 103 ms 93984 KB Output is correct