Submission #1135809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135809		mardehielo	Type Printer (IOI08_printer)	C++20	100 / 100	101 ms	51792 KiB

printer

#include <bits/stdc++.h>

using namespace std;
using ll= long long;
using ld= long double;
using pll=pair<ll, ll>;
using pii=pair<int, int>;
#define inf INT_MAX/2
#define pb push_back
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
# define PI           acos(-1)
# define fst           first
# define snd           second

const int N=1e6+8;
const int ALPHA=26;
int n_nodes=0;
string ans="";
int n, print=0;
int trie[N][ALPHA];
bool word[N]; 
int depth[N];

void insert(string s){
	int node=0;
	for(char it: s){
		if(trie[node][it-'a']==0){
			n_nodes++;
			trie[node][it-'a']=n_nodes;
		}
		node=trie[node][it-'a'];
	}
	word[node]=1; // aqui termina una palabra
}

void dfs(int u){
	for(int i=0; i<26; ++i){
		int v=trie[u][i];
		if(v==0) continue;
		dfs(v);
		depth[u]=max(depth[u], depth[v]);
	}
	depth[u]++;
}

void go(int u){
	vector<pii> son;
	if(word[u]){
		ans+='P';
		print++;
		if(print==n) return;
	}
	for(int i=0; i<26; ++i){
		int v=trie[u][i];
		if(v==0) continue;
		son.pb({v, i}); //es hijo de u, i es el caracter que agrego
	}
	sort(all(son), [&](pii x, pii y){
		return depth[x.fst]<depth[y.fst];
	});
	for(auto& [v,i]: son){
		ans+=(char)(i+'a');
		go(v);
		if(print!=n) ans+="-";
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	vector<string> v(n);
	for(int i=0; i<n; ++i){
		cin>>v[i];
		insert(v[i]);
	}
	dfs(0);
	go(0);
	cout<<ans.size()<<'\n';
	for(auto&t: ans) cout<<t<<'\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