oj.uz

Submission #854951

# Submission time Handle Problem Language Result Execution time Memory
854951 2023-09-29T12:40:05 Z vjudge1 Type Printer (IOI08_printer) C++14
90 / 100
 1000 ms 54940 KB 
// Problem: Type Printer
// Contest: Virtual Judge - OJUZ
// URL: https://vjudge.net/problem/OJUZ-IOI08_printer
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,trie[N][30],tot=1;
bool sum[N],flag[N],last=0;
string s,ll,ans;
void insert(string a){
	int p=1;
	int len=a.size();
	for(int i=0;i<len;i++){
		int ch=a[i]-'a';
		if(!trie[p][ch]) trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	sum[p]=true;
	return;
}
void Mark(string a){
	int p=1;
	int len=a.size();
	for(int i=0;i<len;i++){
		int ch=a[i]-'a';
		p=trie[p][ch];
		flag[p]=true;
	}
	return;
}
void dfs(int now){
	if(sum[now]) ans+='P';
	int x=-1;
	for(int i=0;i<26;i++){
		int t=trie[now][i];
		if(!t) continue;
		if(flag[t]) x=i;
		else{
			ans+=(i+'a');
			dfs(t);
		}
	}
	if(x!=-1){
		ans+=(x+'a');
		dfs(trie[now][x]);
	}
	if(flag[now] && x==-1) last=1;
	if(!last) ans+='-';
	return;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
		if(ll.size()<s.size()) ll=s;
	}
	Mark(ll);
	dfs(1);
	int len=ans.size();
	cout<<len<<endl;
	for(int i=0;i<len;i++) cout<<ans[i]<<endl;
	return 0;
}

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 1 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 348 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 348 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 2 ms 348 KB Output is correct
2 Correct 9 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3420 KB Output is correct
2 Correct 133 ms 7700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 8432 KB Output is correct
2 Correct 48 ms 2128 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 20504 KB Output is correct
2 Correct 863 ms 46492 KB Output is correct
3 Correct 446 ms 24244 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 16088 KB Output is correct
2 Execution timed out 1012 ms 54940 KB Time limit exceeded
3 Halted 0 ms 0 KB -