oj.uz

Submission #685179

# Submission time Handle Problem Language Result Execution time Memory
685179 2023-01-23T16:28:00 Z JANCARAPAN Type Printer (IOI08_printer) C++17
100 / 100
 499 ms 98668 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 = 1e5+1, INF = 1e18, MOD = 1e9+7;
const int S = 30;

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

vector<Node> trie(1);

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) {
    if (!trie[v].nxt.count(cur)) {
      trie[v].nxt[cur] = sz(trie);
      trie.emplace_back();
    }
    v = trie[v].nxt[cur];
    if (i == sz(s) - 1) {
      trie[v].is_word = 1;
    }
  }
}



void solve() {
  int n;
  cin >> n;
  
  map<string,int> is;
  vector<string> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    is[a[i]] = 1;
    add_str(a[i]);
  }
  
  vector<char> ans;
  

  function<void(int)> dfs_set = [&] (int v) {
    for (int i = 0; i < S; i++) {
      if (!trie[v].nxt.count(i)) {
        continue;
      }
      int u = trie[v].nxt[i];
      //if (u == -1) continue;
      dfs_set(u);
      trie[v].height = max(trie[v].height, trie[u].height + 1);
    }
  };
  
  dfs_set(0);
  
  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++) {
      if (!trie[v].nxt.count(i)) {
        continue;
      }
      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++) {
      if (!trie[v].nxt.count(i) || i == who) {
        continue;
      }
      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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1820 KB Output is correct
2 Correct 10 ms 2580 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5832 KB Output is correct
2 Correct 61 ms 12184 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 14456 KB Output is correct
2 Correct 24 ms 4696 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 37808 KB Output is correct
2 Correct 483 ms 82980 KB Output is correct
3 Correct 240 ms 43524 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28148 KB Output is correct
2 Correct 499 ms 98668 KB Output is correct
3 Correct 278 ms 49300 KB Output is correct
4 Correct 441 ms 93284 KB Output is correct