oj.uz

Submission #869174

# Submission time Handle Problem Language Result Execution time Memory
869174 2023-11-03T11:38:24 Z VectorLi Type Printer (IOI08_printer) C++14
20 / 100
 16 ms 3684 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

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

struct Trie {
	int c[N + 1][S], n;
	int g[N + 1];
	string o;
	Trie() : n(0) {
		clean(n);
		o = "";
	}
	void clean(int u) {
		fill(c[u], c[u] + S, 0);
	}
	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;
		}
	}
	void DFS1(int u) {
		g[u] = 1;
		for (int i = 0; i < S; i++) {
			int v = c[u][i];
			if (v > 0) {
				DFS1(v);
				g[u] = max(g[u], g[v] + 1);
			}
		}
	}
	void DFS2(int u) {
		vector<pair<int, int>> a;
		for (int i = 0; i < S; i++) {
			int v = c[u][i];
			if (v > 0) {
				a.push_back({g[v], i});
			}
		}
		sort(a.begin(), a.end());
		for (int i = 0; i < (int) a.size(); i++) {
			int v = c[u][a[i].second];
			o += (char) (a[i].second + 'a');
			DFS2(v);
		}
		if (a.empty()) {
			o += 'P';
		}
		o += '-';
	}
}; 

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 o = t.o;
	int m = (int) o.size();
	int d = t.g[0];
	
	cout << m - d << "\n";
	for (int i = 0; i < m - d; i++) {
		cout << o[i] << "\n";
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 2 ms 3092 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Incorrect 1 ms 2908 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2904 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3164 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3164 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3400 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3684 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3424 KB printed invalid word
2 Halted 0 ms 0 KB -