제출 #1134453

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

printer

  #include <bits/stdc++.h>
  using namespace std;
  int cnt=1,n,h,qc[30];
  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){
    if(s.size()==h) qc[s[0]-'a']=1;
    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];
    }
    node[u].send=1;
  }
  void dfs(int u){
    if(node[u].send==1) ans.push_back('P');
    for(auto i:node[u].link){
      if(u==0 and qc[i]==1) continue;
      ans.push_back(letters[i]);
      dfs(node[u].c[i]);
    }
    if(u==0){
      for(auto i:node[u].link){
        if(qc[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;
  }

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