Submission #855148

#	Time	Username	Problem	Language	Result	Execution time	Memory
855148		vjudge1	Type Printer (IOI08_printer)	C++11	100 / 100	78 ms	51212 KiB

printer

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
using namespace std;
const int SIG = 26, NN = 25004;
struct Trie {
	struct Node {
	  int ch[SIG], mark, end;
	} T[NN * 20];
	int sz = 0;
	void insert(const string& s) {
	  int u = 0;
	  for (char c : s) {
	    int d = c - 'a', &cu = T[u].ch[d];
	    if (!cu) cu = ++sz;
	    u = cu;
	  }
	  T[u].end = true;
	}
	void dfs(int u, string& ans) {
	  const Node& x = T[u];
	  if (x.end) ans += 'P';
	  int mi = -1;
	  for (int i = 0; i < SIG; ++i) {
	    int v = x.ch[i];
	    if (!v) continue;
	    if (T[v].mark) mi = i;
	    else ans += i + 'a', dfs(v, ans);
	  }
	  if (mi != -1) ans += mi + 'a', dfs(x.ch[mi], ans);
	  ans += '-';
	}
} Tr;
int main(void) {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  string s, l;
  _for(i, 0, n) {
    cin >> s, Tr.insert(s);
    if (s.length() > l.length()) l = s;
  }
  int u = 0;
  _for(i, 0, l.size())
    u = Tr.T[u].ch[l[i] - 'a'], Tr.T[u].mark = true;
  s.clear(), Tr.dfs(0, s);
  while (s.back() == '-') s.pop_back();
  cout << s.size() << "\n";
  for (char c : s) cout << c << "\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