oj.uz

Submission #855148

# Submission time Handle Problem Language Result Execution time Memory
855148 2023-09-30T10:15:20 Z vjudge1 Type Printer (IOI08_printer) C++11
100 / 100
 78 ms 51212 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 9 ms 6748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9244 KB Output is correct
2 Correct 5 ms 1888 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 19060 KB Output is correct
2 Correct 71 ms 43276 KB Output is correct
3 Correct 34 ms 22260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15864 KB Output is correct
2 Correct 78 ms 51212 KB Output is correct
3 Correct 39 ms 25340 KB Output is correct
4 Correct 64 ms 48316 KB Output is correct