oj.uz

Submission #855095

# Submission time Handle Problem Language Result Execution time Memory
855095 2023-09-30T07:00:15 Z vjudge1 Type Printer (IOI08_printer) C++14
100 / 100
 77 ms 55052 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<<"\n";
	for(int i=0;i<len;i++) cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
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 #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 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 0 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 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 1 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 4 ms 3420 KB Output is correct
2 Correct 9 ms 7260 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20464 KB Output is correct
2 Correct 64 ms 46352 KB Output is correct
3 Correct 35 ms 24048 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16112 KB Output is correct
2 Correct 77 ms 55052 KB Output is correct
3 Correct 39 ms 27124 KB Output is correct
4 Correct 65 ms 52076 KB Output is correct