oj.uz

Submission #367903

# Submission time Handle Problem Language Result Execution time Memory
367903 2021-02-18T19:04:57 Z sinamhdv Type Printer (IOI08_printer) C++11
100 / 100
 241 ms 96996 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 25100
#define MAXL 500100

int n;
string s[MAXN];
int tn = 1;
int trie[MAXL][26];
int order[MAXL][26];
bool eow[MAXL];
int maxh[MAXL];
vector<char> ops;

void add(const string &s)
{
	int v = 1;
	for (char c : s)
	{
		int b = c - 'a';
		if (!trie[v][b])
			trie[v][b] = ++tn;
		v = trie[v][b];
	}
	eow[v] = true;
}

void dfs1(int v)
{
	FOR(u, 0, 26)
	{
		if (!trie[v][u]) continue;
		dfs1(trie[v][u]);
		maxh[v] = max(maxh[v], maxh[trie[v][u]] + 1);
	}
}

int printed;

void dfs2(int v)
{
	if (eow[v])
	{
		printed++;
		ops.pb('P');
	}
	if (printed == n)
		return;
	FOR(u, 0, 26)
	{
		int c = order[v][u];
		if (c < 0) continue;
		ops.pb(c + 'a');
		dfs2(trie[v][c]);
		if (printed == n)
			return;
		ops.pb('-');
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> s[i];
		add(s[i]);
	}

	dfs1(1);

	FOR(v, 1, tn + 1)
	{
		memset(order[v], -1, sizeof(order[v]));
		vector<int> vec;
		FOR(j, 0, 26)
			if (trie[v][j])
				vec.pb(j);

		sort(all(vec), [&](int x, int y) { return maxh[trie[v][x]] < maxh[trie[v][y]]; });
		FOR(j, 0, (int)vec.size())
			order[v][j] = vec[j];
	}

	dfs2(1);

	cout << ops.size() << endl;

	for (char c : ops)
		cout << c << endl;

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 7 ms 3072 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6636 KB Output is correct
2 Correct 30 ms 12908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14960 KB Output is correct
2 Correct 11 ms 4332 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 35940 KB Output is correct
2 Correct 205 ms 81760 KB Output is correct
3 Correct 110 ms 43112 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 28012 KB Output is correct
2 Correct 241 ms 96996 KB Output is correct
3 Correct 121 ms 48816 KB Output is correct
4 Correct 205 ms 91700 KB Output is correct