oj.uz

Submission #1118592

# Submission time Handle Problem Language Result Execution time Memory
1118592 2024-11-25T17:43:02 Z anuj_anand Type Printer (IOI08_printer) C++17
100 / 100
 176 ms 65820 KB 
#include <bits/stdc++.h>
using namespace std;

/*
*/

using i64 = long long;
const int MOD = 1e9 + 7;

const int K = 26;
struct Vertex {
  vector <int> nxt;
  int ends;
  int max_dep;
  Vertex() : ends{0}, nxt(26, 0), max_dep{0} {}
  void depth(int x) {
    max_dep = max(max_dep, x);
  }
};
vector <Vertex> Trie (1);

void solve() {
  int n;
  cin >> n;

  int root = 0;
  auto insert = [&] (string &s) -> void {
    int node = root;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (Trie[node].nxt[s[i] - 'a'] == 0) {
        Trie[node].nxt[s[i] - 'a'] = Trie.size();
        Trie.push_back(Vertex());
      }
      node = Trie[node].nxt[s[i] - 'a'];
      Trie[node].depth(n - i);
    }
    Trie[node].ends += 1;
  };

  int mx = 0;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    insert(s);
    mx = max(mx, (int) s.size());
  }

  vector <char> res;
  auto dfs = [&] (auto &&dfs, int root) -> void {
    if (Trie[root].ends) {
      for (int tim = 0; tim < Trie[root].ends; tim++) { res.push_back('P'); }
    }
    int maxi = -1;
    int spc = -1;
    for (int c = 0; c < K; ++c) {
      int dep = Trie[Trie[root].nxt[c]].max_dep;
      if (dep > maxi) {
        maxi = dep;
        spc = c;
      }
    }
    for (int c = 0; c < K; ++c) if (c != spc) {
      int v = Trie[root].nxt[c];
      if (v != 0) { res.push_back(c + 'a'); dfs(dfs, v); res.push_back('-'); }
    }
    if (spc != -1 and Trie[root].nxt[spc] != 0) {
      res.push_back(spc + 'a');
      dfs(dfs, Trie[root].nxt[spc]);
      res.push_back('-');
    }
  };

  dfs(dfs, 0);

  while (mx--) { res.pop_back(); }

  cout << res.size() << "\n";
  for (char x : res) {
    cout << x << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int tests = 1;
  // cin >> tests;
  for (int test = 0; test < tests; ++test) {
    solve();
  }
  return 0;
}

Compilation message

printer.cpp: In constructor 'Vertex::Vertex()':
printer.cpp:13:7: warning: 'Vertex::ends' will be initialized after [-Wreorder]
   13 |   int ends;
      |       ^~~~
printer.cpp:12:16: warning:   'std::vector<int> Vertex::nxt' [-Wreorder]
   12 |   vector <int> nxt;
      |                ^~~
printer.cpp:15:3: warning:   when initialized here [-Wreorder]
   15 |   Vertex() : ends{0}, nxt(26, 0), max_dep{0} {}
      |   ^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 2 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1240 KB Output is correct
2 Correct 4 ms 1908 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4048 KB Output is correct
2 Correct 20 ms 8396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9936 KB Output is correct
2 Correct 10 ms 2504 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 24476 KB Output is correct
2 Correct 128 ms 55856 KB Output is correct
3 Correct 69 ms 28844 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 19372 KB Output is correct
2 Correct 142 ms 65820 KB Output is correct
3 Correct 74 ms 32156 KB Output is correct
4 Correct 176 ms 62744 KB Output is correct