oj.uz

Submission #1086373

# Submission time Handle Problem Language Result Execution time Memory
1086373 2024-09-10T11:15:03 Z 4QT0R Type Printer (IOI08_printer) C++17
0 / 100
 36 ms 18876 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+='M';
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1116 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3164 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 7872 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 18876 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 14844 KB Line "M" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -