oj.uz

Submission #855084

# Submission time Handle Problem Language Result Execution time Memory
855084 2023-09-30T06:27:28 Z vjudge1 Type Printer (IOI08_printer) C++14
100 / 100
 76 ms 49496 KB 
// [IOI2008] Type Printer
#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;
}
// P4683 [IOI2008] Type Printer 2.92s /  47.79MB /  1.11KB C++11

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 348 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 600 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20220 KB Output is correct
2 Correct 65 ms 41488 KB Output is correct
3 Correct 32 ms 21488 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 14328 KB Output is correct
2 Correct 76 ms 49496 KB Output is correct
3 Correct 39 ms 24820 KB Output is correct
4 Correct 62 ms 47120 KB Output is correct