oj.uz

Submission #918973

# Submission time Handle Problem Language Result Execution time Memory
918973 2024-01-31T01:50:34 Z cnn008 Type Printer (IOI08_printer) C++17
80 / 100
 38 ms 61948 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=2e5+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 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13144 KB Output is correct
2 Correct 10 ms 15448 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17508 KB Output is correct
2 Correct 6 ms 11096 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28708 KB Output is correct
2 Runtime error 36 ms 61520 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24056 KB Output is correct
2 Runtime error 38 ms 61948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -