oj.uz

Submission #525591

# Submission time Handle Problem Language Result Execution time Memory
525591 2022-02-12T04:39:27 Z AngusWong Type Printer (IOI08_printer) C++17
100 / 100
 221 ms 72328 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

int n;
string s[25001];
vector<pair<pair<char, int>, vector<int> > > trie;
vector<int> l, mx;
string ans;

void insert(string s, int p=0, int t=0){
    if (p==s.length()){
        trie[t].f.s=1;
        return;
    }
    if (!trie[t].s[s[p]-'a']){
        trie.push_back({{s[p], 0}, vector<int>(26, 0)});
        trie[t].s[s[p]-'a']=trie.size()-1;
    }
    insert(s, p+1, trie[t].s[s[p]-'a']);
}

void dfs(int x, int len=0){
    l[x]=len;
    for (int i=0; i<26; i++){
        if (!trie[x].s[i]) continue;
        dfs(trie[x].s[i], len+1);
        if (l[trie[x].s[i]]>=l[x]){
            l[x]=l[trie[x].s[i]], mx[x]=i;
        }
    }
}

void dfs2(int x){
    if (trie[x].f.f!='!') ans+=trie[x].f.f;
    if (trie[x].f.s) ans+='P';
    for (int i=0; i<26; i++){
        if (!trie[x].s[i]) continue;
        if (i!=mx[x]) dfs2(trie[x].s[i]);
    }
    if (mx[x]!=-1) dfs2(trie[x].s[mx[x]]);
    ans+='-';
}

int main() {
    trie.push_back({{'!', 0}, vector<int>(26, 0)});
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> s[i];
        insert(s[i]);
    }
    l=mx=vector<int>(trie.size(), -1);
    dfs(0);
    dfs2(0);
    while (ans.back()=='-') ans.pop_back();
    cout << ans.length() << "\n";
    for (char c: ans) cout << c << "\n";
    vector<string> v;
    string now;
    for (char c: ans){
        assert(c=='-' || c=='P' || (c>='a' && c<='z'));
        if (c=='-') now.pop_back();
        else if (c=='P') v.push_back(now);
        else now+=c;
    }
    assert(v.size()==n);
    sort(v.begin(), v.end());
    sort(s+1, s+n+1);
    for (int i=1; i<=n; i++) assert(v[i-1]==s[i]);
}

Compilation message

printer.cpp: In function 'void insert(std::string, int, int)':
printer.cpp:13:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (p==s.length()){
      |         ~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from printer.cpp:1:
printer.cpp: In function 'int main()':
printer.cpp:67:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     assert(v.size()==n);
      |            ~~~~~~~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 972 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 972 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2116 KB Output is correct
2 Correct 5 ms 2504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5184 KB Output is correct
2 Correct 27 ms 9916 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11828 KB Output is correct
2 Correct 19 ms 4036 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 27888 KB Output is correct
2 Correct 184 ms 61128 KB Output is correct
3 Correct 130 ms 33180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 22388 KB Output is correct
2 Correct 221 ms 72328 KB Output is correct
3 Correct 141 ms 37352 KB Output is correct
4 Correct 196 ms 68396 KB Output is correct