oj.uz

Submission #683908

# Submission time Handle Problem Language Result Execution time Memory
683908 2023-01-19T15:48:24 Z abcdehello Type Printer (IOI08_printer) C++17
100 / 100
 224 ms 146096 KB 
#include <bits/stdc++.h>
using namespace std;
struct node{
	int ch;
	bool print=false,lst=false;
	vector<int> nxt;
};
node trie[1000050];
int n,nxt=1;
vector<string> ss,longest;
vector<char> ans;
void dfs(int u){
	if (u>0) ans.push_back(trie[u].ch);
	if (trie[u].print) ans.push_back('P');
	int lst=-1;
	for (int i=0;i<26;i++){
		if (trie[u].nxt[i]==-1) continue;
		if (trie[trie[u].nxt[i]].lst){
			lst=trie[u].nxt[i]; continue;
		}
		dfs(trie[u].nxt[i]);
	}
	if (lst>0) dfs(lst);
	else ans.push_back('-');
}
bool comp(string a,string b){
	if (a.length()!=b.length()) return a.length()<b.length();
	return a<b;
}
int main(){
	for (int i=0;i<1000050;i++){
		trie[i].nxt.resize(26);
		for (int j=0;j<26;j++){
			trie[i].nxt[j]=-1;
		}
	}
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i=0;i<n;i++){
		string s;
		cin >> s;
		ss.push_back(s);
		int cur=0;
		for (int j=0;j<s.length();j++){
			if (trie[cur].nxt[s[j]-'a']==-1){
				trie[cur].nxt[s[j]-'a']=nxt++;
				trie[nxt-1].ch=s[j];
			}
			cur=trie[cur].nxt[s[j]-'a'];
		}
		trie[cur].print=1;
	}
	sort(ss.begin(),ss.end(),comp);
	string lst=ss.back();
	int cur=0;
	for (int i=0;i<lst.length();i++){
		cur=trie[cur].nxt[lst[i]-'a'];
		trie[cur].lst=1;
	}
	dfs(0);
	ans.pop_back();
	cout << ans.size() << "\n";
	for (auto i:ans) cout << i << "\n";
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j=0;j<s.length();j++){
      |                ~^~~~~~~~~~~
printer.cpp:56:16: 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<lst.length();i++){
      |               ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 141176 KB Output is correct
2 Correct 109 ms 141128 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 141124 KB Output is correct
2 Correct 125 ms 141284 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 141144 KB Output is correct
2 Correct 133 ms 141164 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 141120 KB Output is correct
2 Correct 127 ms 141140 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 141168 KB Output is correct
2 Correct 121 ms 141260 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 141308 KB Output is correct
2 Correct 124 ms 141484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 141492 KB Output is correct
2 Correct 141 ms 141940 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 142272 KB Output is correct
2 Correct 153 ms 142024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 143684 KB Output is correct
2 Correct 224 ms 145256 KB Output is correct
3 Correct 199 ms 144704 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 143496 KB Output is correct
2 Correct 221 ms 146096 KB Output is correct
3 Correct 206 ms 145028 KB Output is correct
4 Correct 205 ms 145856 KB Output is correct