Submission #869174

#	Time	Username	Problem	Language	Result	Execution time	Memory
869174		VectorLi	Type Printer (IOI08_printer)	C++14	20 / 100	16 ms	3684 KiB

printer

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10