Submission #846951

#	Time	Username	Problem	Language	Result	Execution time	Memory
846951		Ivo_12	Type Printer (IOI08_printer)	C++17	100 / 100	171 ms	174336 KiB

printer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

struct TrieNode {
	int edgs[26];
	bool isend;
	pair < int, int > maxlen[26];
	TrieNode() {
		for(int i = 0; i < 26; i++) {
			edgs[i] = -1;
			maxlen[i].f = 0;
			maxlen[i].s = i;
		}
		isend = 0;
	}
};

TrieNode nodes[550010];
int cur = 1;
string s;
int n;
char abc[26];
char prnt[1550010];

void add( string s ) {
	int slen = (int) s.size();
	int curpos = 0;
	for(int i = 0; i < slen; i++) {
		if(nodes[curpos].edgs[s[i]-'a']==-1) {
			nodes[curpos].edgs[s[i]-'a'] = cur;
			cur++;
		}
		nodes[curpos].maxlen[s[i]-'a'].f=max(nodes[curpos].maxlen[s[i]-'a'].f, slen);
		curpos = nodes[curpos].edgs[s[i]-'a'];
	}
	nodes[curpos].isend = 1;
}

void out( int curpos ) {
	sort(nodes[curpos].maxlen, nodes[curpos].maxlen+26);
	if(nodes[curpos].isend) {
		prnt[cur] = 'P';
		cur++;
	}
	for(int i = 0; i < 26; i++) {
		if(nodes[curpos].maxlen[i].f!=0) {
			prnt[cur] = abc[nodes[curpos].maxlen[i].s];
			cur++;
			out(nodes[curpos].edgs[nodes[curpos].maxlen[i].s]);
			prnt[cur] = '-';
			cur++;
		}
	}
}

int main( void ) {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> s;
		add(s);
	}
	abc[0] = 'a';
	for(int i = 1; i < 26; i++) abc[i] = abc[i-1]+1;
//	for(int i = 0; i < 26; i++) cout << nodes[0].maxlen[i].f << "\n";
	cur=0;
	out(0);
	cur-=nodes[0].maxlen[25].f;
	cout << cur << "\n";
	for(int i = 0; i < cur; i++) cout << prnt[i] << "\n";
	
	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: 10 / 10
• Subtask 10: 10 / 10