제출 #1310985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310985		forevpurity	Type Printer (IOI08_printer)	C++20	100 / 100	78 ms	61872 KiB

printer

#include <bits/stdc++.h>
using namespace std;

// clang-format off
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
// clang-format on

const int ALPHA = 26;

struct Trie {
  struct Node {
    int child[ALPHA];
    int count;
    int exist;
    bool mark;
    char c;
    Node() {
      fill(child, child + ALPHA, -1);
      count = exist = 0;
      mark = false;
    }
    int& operator[](int c) { return child[c]; }
  };

  vector<Node> nodes;
  int max_len = 0;
  string max_word = "";
  vector<char> ans;

  Trie() { nodes.emplace_back(); }

  void add(const string& s) {
    int at = 0;
    if (size(s) > max_len) max_len = size(s), max_word = s;
    for (char ch : s) {
      int c = ch - 'a';
      if (nodes[at][c] == -1) {
        nodes[at][c] = size(nodes);
        nodes.emplace_back();
      }
      at = nodes[at][c];
      nodes[at].count++;
      nodes[at].c = char(c + 'a');
    }
    nodes[at].exist++;
  }

  void mark() {
    int at = 0;
    for (char ch : max_word) {
      int c = ch - 'a';
      at = nodes[at][c];
      nodes[at].mark = true;
    }
  }

  void dfs(int at) {
    if (at != 0) ans.pb(nodes[at].c);
    if (nodes[at].exist) ans.pb('P');
    int mark = -1;
    for (int i = 0; i < 26; i++) {
      if (nodes[at][i] == -1) continue;
      if (nodes[nodes[at][i]].mark) {
        mark = nodes[at][i];
        continue;
      }
      dfs(nodes[at][i]);
    }
    if (mark != -1) dfs(mark);
    if (at == 0) return;
    if (!nodes[at].mark) ans.pb('-');
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int TC = 1;
  for (int tc = 1; tc <= TC; tc++) {
    int n;
    cin >> n;
    vector<string> ve(n);
    for (int i = 0; i < n; i++) cin >> ve[i];

    Trie tr;
    for (int i = 0; i < n; i++) tr.add(ve[i]);
    tr.mark();

    tr.dfs(0);

    cout << size(tr.ans) << '\n';
    for (auto ch : tr.ans) cout << ch << '\n';
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10