oj.uz

Submission #869197

# Submission time Handle Problem Language Result Execution time Memory
869197 2023-11-03T13:16:48 Z VectorLi Type Printer (IOI08_printer) C++14
100 / 100
 116 ms 57868 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = 25000 * 20;
const int S = 26;

struct Trie {
	int c[N + 1][S], n;
	bool e[N + 1];
	int d[N + 1];
	string t;
	Trie() : n(0) {
		clean(n);
		t = "";
	}
	void clean(int u) {
		fill(c[u], c[u] + S, 0);
		e[u] = false;
	}
	void insert(string &s) {
		int u = 0;
		for (int i = 0; i < (int) s.size(); i++) {
			int &v = c[u][s[i] - 'a'];
			if (v == 0) {
				n = n + 1;
				clean(n);
				v = n;
			}
			u = v;
		}
		e[u] = true;
	}
	void DFS1(int u) {
		d[u] = 1;
		for (int i = 0; i < S; i++) {
			int v = c[u][i];
			if (v > 0) {
				DFS1(v);
				d[u] = max(d[u], d[v] + 1);
			}
		}
	}
	void DFS2(int u) {
		if (e[u] == true) {
			t += 'P';
		}
		for (int i = 0; i < S; i++) {
			int v = c[u][i];
			if (v > 0 && d[u] > d[v] + 1) {
				t += (char) (i + 'a');
				DFS2(v);
			}
		}
		for (int i = 0; i < S; i++) {
			int v = c[u][i];
			if (v > 0 && d[u] == d[v] + 1) {
				t += (char) (i + 'a');
				DFS2(v);
			}
		}
		t += '-';
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	Trie t;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		t.insert(s);
	}
	
	t.DFS1(0);
	t.DFS2(0);
	
	string s = t.t;
	while (s.back() == '-') {
		s.pop_back();
	}
	cout << s.size() << "\n";
	for (int i = 0; i < (int) s.size(); i++) {
		cout << s[i] << "\n";
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53584 KB Output is correct
2 Correct 28 ms 53600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 53596 KB Output is correct
2 Correct 24 ms 53616 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53596 KB Output is correct
2 Correct 24 ms 53592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53592 KB Output is correct
2 Correct 24 ms 53596 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53532 KB Output is correct
2 Correct 31 ms 53992 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 53628 KB Output is correct
2 Correct 26 ms 53844 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 53848 KB Output is correct
2 Correct 35 ms 54272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 54248 KB Output is correct
2 Correct 30 ms 54108 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55028 KB Output is correct
2 Correct 98 ms 57276 KB Output is correct
3 Correct 65 ms 55792 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 54772 KB Output is correct
2 Correct 116 ms 57868 KB Output is correct
3 Correct 69 ms 56048 KB Output is correct
4 Correct 112 ms 57612 KB Output is correct