oj.uz

Submission #855094

# Submission time Handle Problem Language Result Execution time Memory
855094 2023-09-30T06:58:51 Z vjudge1 Type Printer (IOI08_printer) C++14
100 / 100
 996 ms 55312 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(const 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(const 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 0 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 1 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 344 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 15 ms 1116 KB Output is correct
2 Correct 20 ms 1368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3856 KB Output is correct
2 Correct 124 ms 7252 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 8496 KB Output is correct
2 Correct 43 ms 1884 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 20676 KB Output is correct
2 Correct 844 ms 46560 KB Output is correct
3 Correct 437 ms 23792 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 15928 KB Output is correct
2 Correct 996 ms 55312 KB Output is correct
3 Correct 500 ms 27216 KB Output is correct
4 Correct 946 ms 52240 KB Output is correct