Submission #226661

#	Time	Username	Problem	Language	Result	Execution time	Memory
226661		tushar_2658	Type Printer (IOI08_printer)	C++14	80 / 100	1099 ms	82956 KiB

printer

#include "bits/stdc++.h"
using namespace std;

const int maxn = 1000000;
string s[maxn];
int t[maxn][26], ed[maxn], cnt[maxn];
int node = 0;
int par[maxn];

void insert(string ss){
	int cur = 0;
	int sz = ss.size();
	for(int i = 0; i < sz; ++i){
		int idx = ss[i] - 'a';
		if(t[cur][idx] == 0){
			t[cur][idx] = ++node;
		}
		cur = t[cur][idx];
	}
	ed[cur] = 1;
}

vector<char> v;

void get(int cur){
	cnt[cur] = 1;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			get(t[cur][i]);
			cnt[cur] = max(cnt[cur], cnt[t[cur][i]] + 1);
		}
	}
}

void dfs(int cur){
	if(ed[cur]){
		ed[cur] = 0;
		v.push_back('P');
	}
	vector<pair<int, int>> vv;
	int sz = 0;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			vv.push_back(make_pair(cnt[t[cur][i]], i));
			sz++;
		}
	}
	sort(vv.begin(), vv.end());
	for(int i = 0; i < sz; ++i){
		v.push_back((char)(vv[i].second + 'a'));
		dfs(t[cur][vv[i].second]);
		v.push_back('-');
	}
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> s[i];
		insert(s[i]);
	}
	get(0); 	
	dfs(0);
	int sz = v.size();
	while(v[sz - 1] == '-')--sz;
	cout << sz << endl;
	for(int i = 0; i < sz; ++i){
		cout << v[i] << endl;
	}

	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: 0 / 10
• Subtask 10: 0 / 10