제출 #1134475

#제출 시각아이디문제언어결과실행 시간메모리
1134475unkhoiType Printer (IOI08_printer)C++20
100 / 100
150 ms198996 KiB
  #include <bits/stdc++.h>
  using namespace std;
  int cnt=1,n,h,qc[1000005];
  char letters[30];
  vector <char> ans;
  string t[1000005];
  bool cmp(string a,string b){
    if(a.size()==b.size()) return a<b;
    else return a.size()<b.size();
  }
  struct trie{
    int c[30];
    vector<int> link;
    bool send=0;
  } node[1000005];
  void add_string(string s){
    
    int u=0;
    //if()
    for(char ch:s){
      int x=ch-'a';
      if(node[u].c[x]==0){
        node[u].link.push_back(x);
        node[u].c[x]=cnt;
        cnt++;
      }
      u=node[u].c[x];
      if(s.size()==h) qc[u]=1;
    }
    node[u].send=1;
  }
  void dfs(int u){
    if(node[u].send==1) ans.push_back('P');
    for(auto i:node[u].link){
      if(qc[node[u].c[i]]==1) continue;
      ans.push_back(letters[i]);
      dfs(node[u].c[i]);
    }
    
      for(auto i:node[u].link){
        if(qc[node[u].c[i]]==1){
          ans.push_back(letters[i]);
          dfs(node[u].c[i]);
        }
      
    }
    
    ans.push_back('-');
  }
  int main() 
  {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
     cout.tie(0);
     
     cin>>n;
     for(int i='a';i<='z';i++){
       letters[i-'a']=i;
       //cout<<letters[i-'a'];
     }
     for(int i=0;i<n;i++){
       cin>>t[i];
     }
     sort(t,t+n,cmp);
     h=t[n-1].size();
     for(int i=0;i<n;i++){ 
       add_string(t[i]);
       //if(t[i].size()==h) 
     }
     dfs(0);
     
     while(ans[ans.size()-1]=='-') ans.pop_back();
     cout<<ans.size()<<"\n";
     for(char i:ans) cout<<i<<"\n";
      return 0;
  }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...