oj.uz

Submission #98926

# Submission time Handle Problem Language Result Execution time Memory
98926 2019-02-27T13:21:04 Z luciocf Type Printer (IOI08_printer) C++14
100 / 100
 288 ms 99692 KB 
#include <bits/stdc++.h>

using namespace std;

struct node
{
	node *b[26];
	int sz;
	bool end;
};

int n, qtd;
vector<char> ans;

void insert(node *at, string const &s)
{
	int add = -1;

	for (char a: s)
	{
		at->sz = max(at->sz, (int)s.size()-(++add));

		if (!at->b[a-'a']) at->b[a-'a'] = new node();

		at = at->b[a-'a'];
	}

	at->sz = max(at->sz, 1);
	at->end = true;
}

void dfs(node *at, char c)
{
	if (c != '*') ans.push_back(c);
	if (at->end) ans.push_back('P'), qtd++;

	set< pair<int, int> > S;

	for (int i = 0; i < 26; i++)
	{
		if (!at->b[i]) continue;

		S.insert({at->b[i]->sz, i});
	}

	for (auto p: S)
		dfs(at->b[p.second], (char)(p.second+'a'));

	if (qtd < n) ans.push_back('-');
}

int main(void)
{
	cin >> n;

	node *t = new node();

	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;

		insert(t, s);
	}

	dfs(t, '*');

	cout << ans.size() << "\n";
	for (auto c: ans) cout << c << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1792 KB Output is correct
2 Correct 9 ms 2304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6016 KB Output is correct
2 Correct 40 ms 12664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14840 KB Output is correct
2 Correct 24 ms 3456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 36768 KB Output is correct
2 Correct 191 ms 83816 KB Output is correct
3 Correct 131 ms 43348 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 28852 KB Output is correct
2 Correct 288 ms 99692 KB Output is correct
3 Correct 148 ms 49144 KB Output is correct
4 Correct 224 ms 94068 KB Output is correct