oj.uz

Submission #1118585

# Submission time Handle Problem Language Result Execution time Memory
1118585 2024-11-25T17:34:17 Z anuj_anand Type Printer (IOI08_printer) C++17
0 / 100
 70 ms 24668 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';
  }
  cout << "\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();
  }
}

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1608 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 4052 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9920 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 24668 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 19496 KB Expected EOF
2 Halted 0 ms 0 KB -