oj.uz

Submission #989452

# Submission time Handle Problem Language Result Execution time Memory
989452 2024-05-28T07:58:55 Z huutuan Type Printer (IOI08_printer) C++14
100 / 100
 97 ms 61240 KB 
#include<bits/stdc++.h>

using namespace std;

struct Node{
   int cnt, end;
   int nxt[26];
   Node (){
      cnt=0; end=0;
      memset(nxt, -1, sizeof nxt);
   }
};

struct Trie{
   vector<Node> t;
   Trie (){
      t.emplace_back();
   }
   void add_string(const string &s, int x){
      int id=0;
      for (char cc:s){
         t[id].cnt+=x;
         int c=cc-'a';
         if (t[id].nxt[c]==-1){
            t[id].nxt[c]=t.size();
            t.emplace_back();
         }
         id=t[id].nxt[c];
      }
      t[id].cnt+=x;
      ++t[id].end;
   }
   void dfs(int id, vector<char> &ans){
      for (int i=0; i<(int)t[id].end; ++i) ans.push_back('P');
      for (int c=0; c<26; ++c) if (t[id].nxt[c]!=-1 && !t[t[id].nxt[c]].cnt){
         ans.push_back('a'+c);
         dfs(t[id].nxt[c], ans);
         ans.push_back('-');
      }
      for (int c=0; c<26; ++c) if (t[id].nxt[c]!=-1 && t[t[id].nxt[c]].cnt){
         ans.push_back('a'+c);
         dfs(t[id].nxt[c], ans);
      }
   }
} trie;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int n;
   cin >> n;
   vector<string> v(n);
   for (auto &i:v) cin >> i;
   int id=max_element(v.begin(), v.end(), [&](string s, string t){ return s.size()<t.size(); })-v.begin();
   v.push_back(v[id]);
   v.erase(v.begin()+id);
   for (int i=0; i<n-1; ++i) trie.add_string(v[i], 0);
   trie.add_string(v.back(), 1);
   vector<char> ans;
   trie.dfs(0, ans);
   cout << ans.size() << '\n';
   for (char c:ans) cout << c << '\n';
   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1572 KB Output is correct
2 Correct 3 ms 2412 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5892 KB Output is correct
2 Correct 11 ms 8300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9140 KB Output is correct
2 Correct 6 ms 3360 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31384 KB Output is correct
2 Correct 85 ms 60704 KB Output is correct
3 Correct 43 ms 32200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17856 KB Output is correct
2 Correct 97 ms 61100 KB Output is correct
3 Correct 53 ms 32444 KB Output is correct
4 Correct 87 ms 61240 KB Output is correct