Submission #1093875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093875		vjudge1	Type Printer (IOI08_printer)	C++17	30 / 100	28 ms	18896 KiB

printer

    #include<bits/stdc++.h>
    //SHORTEST CODE:::::
    #define ll long long
    #define ull unsigned long long
    #define vi vector<int> 
    #define vll vector<long long> 
    #define PB push_back
    #define snd second
    #define fst first
    #define ii pair<int, int>
    #define MP make_pair
    #define forn(i,n) for(int i=0;i<n;++i)
    #define forsn(i,s,n) for(int i=s; i<n; ++i)
    #define SIZE(c) int((c).size())
    #define all(x) x.begin(), x.end()
    #define endl '\n'
    #define yes cout<<"Yes\n"
    #define no cout<<"No\n"
    #define imp(x) {for(auto __:x)cout<<__<<" "; cout<<"\n";}
    //DEBUG:::::
    #define DBG(x) cerr << #x << " = " << (x) << endl
    #define RAYA cerr << "===============================" << endl
     
    using namespace std;
         
    inline void FIO() {ios_base::sync_with_stdio(false); cin.tie(NULL);}
     
    int dx[4]={0, 0, 1, -1};
    int dy[4]={1, -1, 0, 0};
    /*Cosas a tener en cuenta:
    -Mantenlo Simple
    -Leer TODO el enunciado*/
     
    const int mxn=1e5*2+10, M=1e9+7;
    /*ll fact[mxn];
     
    ll pw(ll a, ll b){
    	if(b==0)return 1;
    	if(b%2==0)return pw(a*a%M,b/2)%M;
    	else return (a*pw(a*a%M,b/2))%M;
    }
     
    ll C(ll n, ll k){
    	if(n<k)return 0LL;
    	return (fact[n]*pw((fact[k]*fact[n-k])%M, M-2))%M;
    }*/
     
    const int maxnodos=500001;
    int trie[maxnodos][26];
    bool fin[maxnodos];
    bool distances[maxnodos];
    int nxt=2;
    vector<char> res;
     
    void add(string s, int raiz, string x){
    	int nodo=raiz;
    	for(int i=0; i<SIZE(s); i++){
    		int ch=s[i]-'a';
    		if(trie[nodo][ch]==0)trie[nodo][ch]=nxt++;
    		if(s==x){
    			distances[trie[nodo][ch]]=1;
    		}
    		nodo=trie[nodo][ch];
    	}
    	fin[nodo]=true;
    }
     
    void dfs(int nodo){
    	if(fin[nodo]){
    		res.PB('P');
    	}
    	for(int i=0; i<26; i++){
    		if(trie[nodo][i]==0)continue;
    		if(nodo==1 and distances[trie[nodo][i]]){
    			for(int j=0; j<26; j++){
    				if(!distances[trie[nodo][j]] and trie[nodo][j]){
    					res.PB(j+'a');
    					dfs(trie[nodo][j]);
    					res.PB('-');
    				}
    			}
    			res.PB(i+'a');
    			dfs(trie[nodo][i]);
    			res.PB('-');
    		}
    		else if(nodo!=1){
    			res.PB(i+'a');
    			dfs(trie[nodo][i]);
    			res.PB('-');
    		}
    	}
    }
     
    int main(){FIO();
    	int n;cin>>n;
    	vector<string> v(n); 
    	pair<int, string> s;
    	forn(i,n){
    		cin>>v[i];
    		s=max(s, {SIZE(v[i]), v[i]});
    	}
    	forn(i,n){
    		add(v[i], 1, s.snd);
    	}
    	dfs(1);
    	while(res.back()=='-')res.pop_back();
    	cout<<SIZE(res)<<endl;
    	forn(i,SIZE(res)){
    		cout<<res[i]<<endl;
    	}
    }
     

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 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