oj.uz

Submission #367889

# Submission time Handle Problem Language Result Execution time Memory
367889 2021-02-18T18:39:21 Z sinamhdv Type Printer (IOI08_printer) C++11
0 / 100
 83 ms 35752 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) 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)
	{
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Incorrect 1 ms 1152 KB didn't print every word

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1152 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1132 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1132 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1260 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2668 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6636 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 14956 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 35752 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 28016 KB didn't print every word
2 Halted 0 ms 0 KB -