Submission #918969

#	Time	Username	Problem	Language	Result	Execution time	Memory
918969		cnn008	Type Printer (IOI08_printer)	C++17	0 / 100	11 ms	15704 KiB

printer

#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=5e4+5;
const int mod=1e9+7;

int n,len;
string ss,s[N],ans;
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;
		}
	}
	void dfs(int v, string &ans){
		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],ans);
			}
		}
		if(markd!=-1){
			ans.push_back(char('a'+markd));
			dfs(node[v].child[markd],ans);
		}
		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,ans);
	for(auto c: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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10