oj.uz

Submission #1086374

# Submission time Handle Problem Language Result Execution time Memory
1086374 2024-09-10T11:15:38 Z 4QT0R Type Printer (IOI08_printer) C++17
100 / 100
 98 ms 50448 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3164 KB Output is correct
2 Correct 13 ms 6492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7712 KB Output is correct
2 Correct 6 ms 2136 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18760 KB Output is correct
2 Correct 79 ms 42516 KB Output is correct
3 Correct 42 ms 22180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14844 KB Output is correct
2 Correct 98 ms 50448 KB Output is correct
3 Correct 47 ms 25072 KB Output is correct
4 Correct 82 ms 47632 KB Output is correct