제출 #1133685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133685		unkhoi	Type Printer (IOI08_printer)	C++20	10 / 100	140 ms	194576 KiB

printer

  #include <bits/stdc++.h>
  using namespace std;
  int cnt=1,n;
  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;
    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];
    }
    node[u].send=1;
  }
  void dfs(int u){
    if(node[u].send==1) ans.push_back('P');
    for(auto i:node[u].link){
      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);
     for(int i=0;i<n;i++) add_string(t[i]);
     dfs(0);
     
     while(ans[ans.size()-1]=='-') ans.pop_back();
     cout<<ans.size()<<"\n";
     for(char i:ans) cout<<i<<"\n";
      return 0;
  }

• Subtask 1: 10 / 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