oj.uz

답안 #685224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685224 2023-01-23T17:25:17 Z JANCARAPAN Type Printer (IOI08_printer) C++17
100 / 100
 197 ms 173264 KB 
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr <<__func__<<":"<<" [" << #x << "] = ["; _print(x); /*cerr << "\e[39m" << endl;*/
#else
#define dbg(x...)
#endif


#define ll long long
#define ld long double
#define int long long


#define fi first
#define se second
#define pb push_back
#define ii pair<ll,ll>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (ll)x.size()
#define endl '\n'

const ll N = 25000, INF = 1e18, MOD = 1e9+7;
const int S = 26;

int t = 0;

struct Node {
  vector<int> nxt;
  bool is_word = 0;
  int height = 0;
  Node() {
    nxt.assign(S, -1);
  }
};

//vector<Node> trie(1);
Node trie[N * S];

void add_str(string& s) {
  int v = 0;
  for (int i = 0; i < sz(s); i++) {
    int cur = s[i] - 'a';
    if (trie[v].nxt[cur] == -1) {
      trie[v].nxt[cur] = ++t;
      //trie[v].nxt[cur] = sz(trie);
      //trie.emplace_back();
    }
    v = trie[v].nxt[cur];
    trie[v].height = max(trie[v].height, sz(s) - i);
    if (i == sz(s) - 1) {
      trie[v].is_word = 1;
    }
  }
}



void solve() {
  int n;
  cin >> n;
  
  vector<string> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    add_str(a[i]);
  }
  
  vector<char> ans;
  
  function<void(int)> dfs = [&] (int v) {
    if (trie[v].is_word) ans.emplace_back('P');
    
    int mx = -1, who = -1;
    for (int i = 0; i < S; i++) {
      int u = trie[v].nxt[i];
      if (u == -1) continue;
      if (mx < trie[u].height) {
        mx = trie[u].height;
        who = i;
      }
    }
    
    //dbg(char('a' + who), mx)
    
    for (int i = 0; i < S; i++) {
      int u = trie[v].nxt[i];
      if (u == -1 || i == who) continue;
      ans.emplace_back(char('a' + i));
      dfs(u);
    }
    if (who != -1) {
      ans.emplace_back(char('a' + who));
      dfs(trie[v].nxt[who]);
    }
    ans.emplace_back('-');
  };
  
  dfs(0);
  
  while (ans.back() == '-') ans.pop_back();
  
  cout << sz(ans) << endl;
  for (int i = 0; i < sz(ans); i++) {
    cout << ans[i] << endl;
  }
  
  // READ AT THE BOTTOM PLS!
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--) solve();
  return 0;
}

/* stuff you should look for
  * int overflow, array bounds
  * special cases (n = 1?)
  * READ CONSTRAINTS
  * reset variables?
  * STAY ORGANIZED
*/

/* 
 Suppose I did find such a solution, what would it look like? 
 What characteristics it would have? 
 Can we toy around with such a solution so that it remains optimal?
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 168192 KB Output is correct
2 Correct 88 ms 168156 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 168208 KB Output is correct
2 Correct 87 ms 168212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 168108 KB Output is correct
2 Correct 87 ms 168172 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 168212 KB Output is correct
2 Correct 95 ms 168096 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 168136 KB Output is correct
2 Correct 88 ms 168260 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 168372 KB Output is correct
2 Correct 91 ms 168268 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 168472 KB Output is correct
2 Correct 103 ms 169052 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 169156 KB Output is correct
2 Correct 94 ms 168976 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 170288 KB Output is correct
2 Correct 176 ms 172612 KB Output is correct
3 Correct 139 ms 171576 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 170040 KB Output is correct
2 Correct 197 ms 173264 KB Output is correct
3 Correct 140 ms 171996 KB Output is correct
4 Correct 176 ms 173228 KB Output is correct