# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
445772 | 2021-07-19T14:12:25 Z | dxz05 | Type Printer (IOI08_printer) | C++14 | 195 ms | 83508 KB |
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; #define SZ(x) (int)(x).size() const int MAXN = 1e6 + 3e2; string str[MAXN]; int next_free = 2; int trie[MAXN][26], term[MAXN]; int mx[MAXN]; void add(int ind, int val, string &s){ int v = 1; for (int i = 0; i < s.size(); i++){ int x = s[i] - 'a'; if (trie[v][x] == 0) trie[v][x] = next_free++; v = trie[v][x]; mx[v] = max(mx[v], val); } term[v] = 1; } vector<char> ans; int n, cnt = 0; void solve(int v){ if (term[v]){ cnt++; ans.push_back('P'); if (cnt == n){ printf("%d\n", SZ(ans)); for (char c : ans) printf("%c\n", c); exit(0); } } int best = 0, ind = -1; for (int i = 0; i < 26; i++){ if (trie[v][i] != 0){ if (mx[trie[v][i]] > best){ best = mx[trie[v][i]]; ind = i; } } } for (int i = 0; i < 26; i++){ if (trie[v][i] != 0 && ind != i){ ans.push_back('a' + i); solve(trie[v][i]); ans.push_back('-'); } } if (ind != -1){ ans.push_back('a' + ind); solve(trie[v][ind]); ans.push_back('-'); } } int main(){ //ios_base::sync_with_stdio(false); //cin.tie(nullptr); cout.tie(nullptr); scanf("%d", &n); int ind = 0; for (int i = 1; i <= n; i++){ char c[25]; scanf("%s", &c); int len = strlen(c); str[i].resize(len); for (int j = 0; j < len; j++) str[i][j] = c[j]; //cout << str[i] << endl; if (str[i].size() > str[ind].size()) ind = i; } string longest = str[ind]; for (int i = 1; i <= n; i++){ int j = 0; while (j < str[i].size() && str[i][j] == longest[j]) j++; add(i, j, str[i]); //cout << j << ' ' << str[i] << endl; } solve(1); return 0; } /** 3 print the poem */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 31564 KB | Output is correct |
2 | Correct | 23 ms | 31568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 31640 KB | Output is correct |
2 | Correct | 19 ms | 31532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 31564 KB | Output is correct |
2 | Correct | 20 ms | 31636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 31564 KB | Output is correct |
2 | Correct | 19 ms | 31632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 31616 KB | Output is correct |
2 | Correct | 20 ms | 31948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 32304 KB | Output is correct |
2 | Correct | 25 ms | 32600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 34508 KB | Output is correct |
2 | Correct | 38 ms | 38004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 39084 KB | Output is correct |
2 | Correct | 30 ms | 33220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 72 ms | 50372 KB | Output is correct |
2 | Correct | 142 ms | 75188 KB | Output is correct |
3 | Correct | 96 ms | 54548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 60 ms | 46136 KB | Output is correct |
2 | Correct | 195 ms | 83508 KB | Output is correct |
3 | Correct | 99 ms | 57696 KB | Output is correct |
4 | Correct | 148 ms | 80700 KB | Output is correct |