oj.uz

Submission #863101

# Submission time Handle Problem Language Result Execution time Memory
863101 2023-10-19T15:24:03 Z mgl_diamond Type Printer (IOI08_printer) C++17
100 / 100
 107 ms 58812 KB 
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define fi first
#define se second
#define ins push_back
#define vec vector
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(i, v) for(auto &i : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()

struct node {
	int child[26], en = 0, dep = 0;
	node() { memset(child, -1, sizeof(child)); }
};

vec<node> trie;
string ret;

void add(int i, int u, const string &s) {
	if (i == sz(s)) {
		trie[u].en += 1;
		return;
	}
	int ch = s[i]-'a';

	if (trie[u].child[ch] == -1) {
		trie[u].child[ch] = sz(trie);
		trie.ins(node());
	}

	add(i+1, trie[u].child[ch], s);
	trie[u].dep = max(trie[u].dep, trie[trie[u].child[ch]].dep + 1);
}

void dfs(int u) {
	for(int i=0; i<trie[u].en; ++i) ret.ins('P');
	
	vec<int> order;
	for(int i=0; i<26; ++i) if (trie[u].child[i] != -1) 
		order.ins(i);
	
	sort(all(order), [&](int i, int j){
		return trie[trie[u].child[i]].dep < trie[trie[u].child[j]].dep;
	});

	for(int i : order) {
		ret.ins(i + 'a');
		dfs(trie[u].child[i]);
		ret.ins('-');
	}
}

void solve() {
	trie.ins(node());
	int n;
	cin >> n;
	foru(i, 1, n) {
		string s;
		cin >> s;
		add(0, 0, s);
	}
	dfs(0);
	while (!ret.empty() && ret.back() == '-') ret.pop_back();
	cout << ret.size() << "\n";
    for(char c : ret) cout << c << "\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 344 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 1 ms 604 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5584 KB Output is correct
2 Correct 16 ms 7884 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8652 KB Output is correct
2 Correct 7 ms 2388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 29376 KB Output is correct
2 Correct 91 ms 58556 KB Output is correct
3 Correct 48 ms 30660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16836 KB Output is correct
2 Correct 107 ms 58780 KB Output is correct
3 Correct 57 ms 29892 KB Output is correct
4 Correct 106 ms 58812 KB Output is correct