oj.uz

Submission #918974

# Submission time Handle Problem Language Result Execution time Memory
918974 2024-01-31T01:51:10 Z cnn008 Type Printer (IOI08_printer) C++17
100 / 100
 113 ms 149772 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define cebug(x) cerr<<"["<<#x<<"] = "<<x<<endl
#define cebugp(x,y) cerr<<"["<<#x<<" "<<#y<<"] = "<<x<<"  "<<y<<endl

const int N=3e6+5;
const int mod=1e9+7;

int n,len;
string ss,s[N];
struct Trie{
	struct Node{
		int child[26];
		int cnt,end,mark;
	}node[N];
	int nx=1;
	void init(){
		for(int i=0; i<=nx; i++){
			node[i].cnt=node[i].end=node[i].mark=0;
			memset(node[i].child,-1,sizeof(node[i].child));
		}
		nx=1;
	}
	void insert(string s){
		int v=0;
		for(auto c:s){
			if(node[v].child[c-'a']==-1){
				node[v].child[c-'a']=nx++;
				node[nx].cnt=node[nx].end=node[nx].mark=0;
				memset(node[nx].child,-1,sizeof(node[nx].child));
			}
			v=node[v].child[c-'a'];
			node[v].cnt++;
		}
		node[v].end++;
	}
	void mark(string s){
		int v=0;
		for(auto c:s){
			v=node[v].child[c-'a'];
			node[v].mark=1;
		}
	}
	string ans;
	void dfs(int v){
		while(node[v].end--) ans.push_back('P');
		int markd=-1;
		for(int i=0; i<26; i++){
			if(node[v].child[i]!=-1){
				if(node[node[v].child[i]].mark){
					markd=i;
					continue;
				}
				ans.push_back(char('a'+i));
				dfs(node[v].child[i]);
			}
		}
		if(markd!=-1){
			ans.push_back(char('a'+markd));
			dfs(node[v].child[markd]);
		}
		ans.push_back('-');
	}
};
Trie trie;
void sol(){
	trie.init();
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>s[i];
		trie.insert(s[i]);
		if((int)s[i].size()>len){
			len=((int)s[i].size());
			ss=s[i];
		}
	}
	trie.mark(ss);
	trie.dfs(0);
	while(trie.ans.back()=='-') trie.ans.pop_back();
	cout<<(int)trie.ans.size()<<"\n";
	for(auto c:trie.ans) cout<<c<<"\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    int t=1;
    //cin>>t; 
    while(t--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}
/**  /\_/\
*   (= ._.)
*   / >💖 \>💕
**/

Compilation message

printer.cpp:97:9: warning: "/*" within comment [-Wcomment]
   97 | /**  /\_/\
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 96088 KB Output is correct
2 Correct 28 ms 96096 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 96080 KB Output is correct
2 Correct 29 ms 96088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 96080 KB Output is correct
2 Correct 30 ms 96088 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 96080 KB Output is correct
2 Correct 29 ms 96080 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 95996 KB Output is correct
2 Correct 30 ms 96604 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 96856 KB Output is correct
2 Correct 30 ms 97112 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 99152 KB Output is correct
2 Correct 41 ms 102736 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 103916 KB Output is correct
2 Correct 33 ms 97880 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 115436 KB Output is correct
2 Correct 102 ms 141048 KB Output is correct
3 Correct 67 ms 120044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 111088 KB Output is correct
2 Correct 113 ms 149772 KB Output is correct
3 Correct 70 ms 123372 KB Output is correct
4 Correct 94 ms 147208 KB Output is correct