oj.uz

Submission #756926

# Submission time Handle Problem Language Result Execution time Memory
756926 2023-06-12T11:24:35 Z SanguineChameleon Type Printer (IOI08_printer) C++17
100 / 100
 204 ms 106556 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct node {
	node *ch[26] = {};
	bool flag = false;
	int mx = 0;
	int best = -1;
};

node *root = new node();

void dfs1(node *cur) {
	for (int i = 0; i < 26; i++) {
		if (cur->ch[i]) {
			dfs1(cur->ch[i]);
		}
	}
	for (int i = 0; i < 26; i++) {
		if (cur->ch[i] && cur->ch[i]->mx + 1 > cur->mx) {
			cur->mx = cur->ch[i]->mx + 1;
			cur->best = i;
		}
	}
}

vector<char> res;

void dfs2(node *cur, bool up) {
	if (cur->flag) {
		res.push_back('P');
	}
	if (cur->best != -1) {
		for (int i = 0; i < 26; i++) {
			if ((up || i != cur->best) && cur->ch[i]) {
				res.push_back((char)('a' + i));
				dfs2(cur->ch[i], true);
				res.push_back('-');
			}
		}
		if (!up) {
			res.push_back((char)('a' + cur->best));
			dfs2(cur->ch[cur->best], false);
		}
	}
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		node *cur = root;
		for (auto c: s) {
			int d = c - 'a';
			if (!cur->ch[d]) {
				cur->ch[d] = new node();
			}
			cur = cur->ch[d];
		}
		cur->flag = true;
	}
	dfs1(root);
	dfs2(root, false);
	cout << res.size() << '\n';
	for (auto c: res) {
		cout << c << '\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 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 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 324 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 444 KB Output is correct
2 Correct 3 ms 1220 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1860 KB Output is correct
2 Correct 4 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6348 KB Output is correct
2 Correct 30 ms 13340 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15732 KB Output is correct
2 Correct 10 ms 3540 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 39164 KB Output is correct
2 Correct 149 ms 89564 KB Output is correct
3 Correct 76 ms 46276 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 30540 KB Output is correct
2 Correct 204 ms 106556 KB Output is correct
3 Correct 83 ms 52412 KB Output is correct
4 Correct 146 ms 100436 KB Output is correct