oj.uz

Submission #510076

# Submission time Handle Problem Language Result Execution time Memory
510076 2022-01-14T16:23:56 Z BERNARB01 Type Printer (IOI08_printer) C++17
100 / 100
 236 ms 58292 KB 
#include <bits/stdc++.h>

using namespace std;

vector<char> res;

struct trie {
  vector<array<int, 26>> T;
  vector<int> E, d, mxd;
  trie() {
    T.resize(1);
    E.resize(1);
    d.resize(1);
    mxd.resize(1);
  }
  void inserT(const string& s) {
    int t = 0;
    for (char c : s) {
      c -= 'a';
      if (!T[t][c]) {
        T[t][c] = T.size();
        T.emplace_back();
        E.emplace_back(0);
        d.push_back(0);
        mxd.push_back(0);
      }
      t = T[t][c];
    }
    E[t] += 1;
  }
  void dfs0(int t) {
    mxd[t] = d[t];
    for (int j = 0; j < 26; j++) {
      if (T[t][j]) {
        d[T[t][j]] = 1 + d[t];
        dfs0(T[t][j]);
        mxd[t] = max(mxd[t], mxd[T[t][j]]);
      }
    }
  }
  void DFS(int t) {
    vector<int> order(26);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return mxd[T[t][i]] < mxd[T[t][j]];
    });
    for (int k = 0; k < E[t]; k++) {
      res.push_back('P');
    }
    for (int j : order) {
      if (T[t][j]) {
        res.push_back(char(j + 'a'));
        DFS(T[t][j]);
        res.push_back('-');
      }
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  trie T;
  for (int i = 0; i < n; i++) {
    string foo;
    cin >> foo;
    T.inserT(foo);
  }
  T.dfs0(0);
  T.DFS(0);
  while (res.back() == '-') {
    res.pop_back();
    assert(!res.empty());
  }
  cout << res.size() << '\n';
  for (auto& x : res) {
    cout << x << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1216 KB Output is correct
2 Correct 4 ms 2076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3928 KB Output is correct
2 Correct 29 ms 7508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8252 KB Output is correct
2 Correct 10 ms 2196 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 28976 KB Output is correct
2 Correct 197 ms 57768 KB Output is correct
3 Correct 101 ms 29004 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16012 KB Output is correct
2 Correct 236 ms 58292 KB Output is correct
3 Correct 115 ms 29548 KB Output is correct
4 Correct 217 ms 58228 KB Output is correct