oj.uz

Submission #855142

# Submission time Handle Problem Language Result Execution time Memory
855142 2023-09-30T10:04:36 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 74 ms 49932 KB 
// Problem: D - Type Printer
// Contest: Virtual Judge - 2023榕阳提高级国庆集训-day1
// URL: https://vjudge.net/contest/584200#problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;

const int SIG = 26, NN = 25000;

struct Node
{
	int	 ch[SIG];
	bool mark, end;
} T[NN * 20];

int sz = 0;

void insert(const string &s)
{
	int u = 0;
	for (char c : s)
	{
		int d = c - 'a', &cu = T[u].ch[d];
		if (!cu)
			cu = ++sz;
		u = cu;
	}
	T[u].end = true;
}

void dfs(int u, string &ans)
{
	const Node &x = T[u];
	if (x.end)
		ans += 'P';
	int mi = -1;
	for (int i = 0; i < SIG; ++i)
	{
		int v = x.ch[i];
		if (!v)
			continue;
		if (T[v].mark)
			mi = i;
		else
			ans += i + 'a', dfs(v, ans);
	}
	if (mi != -1)
		ans += mi + 'a', dfs(x.ch[mi], ans);
	ans += '-';
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	string s, l;
	for (int i = 0; i < n; ++i)
	{
		cin >> s, insert(s);
		if (s.length() > l.length())
			l = s;
	}
	for (size_t i = 0, u = 0; i < l.size(); i++)
		u = T[u].ch[l[i] - 'a'], T[u].mark = true;
	s.clear(), dfs(0, s);
	while (s.back() == '-')
		s.pop_back();
	cout << s.size() << "\n";
	for (char c : s)
		cout << c << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 9 ms 6492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7664 KB Output is correct
2 Correct 5 ms 2136 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20212 KB Output is correct
2 Correct 62 ms 42116 KB Output is correct
3 Correct 33 ms 22012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14584 KB Output is correct
2 Correct 74 ms 49932 KB Output is correct
3 Correct 40 ms 24816 KB Output is correct
4 Correct 60 ms 47116 KB Output is correct