Submission #1086374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086374		4QT0R	Type Printer (IOI08_printer)	C++17	100 / 100	98 ms	50448 KiB

printer

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

int trie[1000003][26];
bool slo[1000003];
int iter=1;
int dep[1000003];

int lft;
string ans;

void build(string s){
	int v=1;
	for (int i = 0; i<s.size(); i++){
		if (!trie[v][s[i]-'a'])trie[v][s[i]-'a']=++iter;
		v=trie[v][s[i]-'a'];
	}
	slo[v]=true;
}
void prep(int v){
	for (int i = 0; i<26; i++)if (trie[v][i]){
		prep(trie[v][i]);
		dep[v]=max(dep[v],dep[trie[v][i]]+1);
	}
}
void dfs(int v){
	if (slo[v]){
		ans+='P';
		lft--;
	}
	vector<pair<int,int>> kra;
	for (int i = 0; i<26; i++)if (trie[v][i])kra.push_back({trie[v][i],i});
	sort(kra.begin(),kra.end(),[](pair<int,int> a, pair<int,int> b){return dep[a.first]<dep[b.first];});
	for (auto [u,i] : kra){
		ans+='a'+i;
		dfs(u);
	}
	if (lft)ans+='-';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	lft=n;
	string s;
	for (int i = 1; i<=n; i++){
		cin >> s;
		build(s);
	}
	prep(1);
	dfs(1);
	cout << ans.size() << '\n';
	for (int i = 0; i<ans.size(); i++)cout << ans[i] << '\n';
}

Compilation message (stderr)

printer.cpp: In function 'void build(std::string)':
printer.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i<s.size(); i++){
      |                  ~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i<ans.size(); i++)cout << ans[i] << '\n';
      |                  ~^~~~~~~~~~~

• 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