Submission #528085

#	Time	Username	Problem	Language	Result	Execution time	Memory
528085		aggrovector	Type Printer (IOI08_printer)	C++17	20 / 100	425 ms	19060 KiB

printer

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,trie[500005][26],last[500005],idx,i,e[500005];
string a[25005];

void insert(string x) {
	int l=x.length();
	int p=0;
	for (int i=0;i<l;i++) {
		if (trie[p][x[i]-'a']==0) {
			idx++;
			trie[p][x[i]-'a']=idx;
			p=trie[p][x[i]-'a'];
		}
		else {
			p=trie[p][x[i]-'a'];
		}
	}
	e[p]=1;
}

void insert1(string x) {
	int l=x.length();
	int p=0;
	for (int i=0;i<l;i++) {
		if (trie[p][x[i]-'a']==0) {
			idx++;
			trie[p][x[i]-'a']=idx;
			p=trie[p][x[i]-'a'];
		}
		else {
			p=trie[p][x[i]-'a'];
		}
		last[p]=1;
	}
	e[p]=1;
}

bool cmp(string x, string y) {
	int lx=x.length();
	int ly=y.length();
	return lx<ly;
}

void dfs(int x) {
	for (int i=0;i<26;i++) {
		if (trie[x][i]>0 && last[trie[x][i]]==0) {
			cout << char(i+'a') << endl;
			dfs(trie[x][i]);
		}
	}
	for (int i=0;i<26;i++) {
		if (trie[x][i]>0 && last[trie[x][i]]==1) {
			cout << char(i+'a') << endl;
			dfs(trie[x][i]);
		}
	}
	if (e[x]==1) {
		cout << 'P' << endl;
	}
	if (last[x]==0) {
		cout << '-' << endl;
	}
}

int main() {
	cin >> n;
	for (i=1;i<=n;i++) {
		cin >> a[i];
	}
	sort(a+1,a+1+n,cmp);
	for (i=1;i<n;i++) {
		insert(a[i]);
	}
	insert1(a[n]);
	last[0]=1;
	cout << idx*2+n-a[n].length() << endl;
	dfs(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