oj.uz

Submission #953207

# Submission time Handle Problem Language Result Execution time Memory
953207 2024-03-25T17:18:36 Z AverageAmogusEnjoyer Type Printer (IOI08_printer) C++17
100 / 100
 88 ms 60168 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i,T j) { return i > j ? i = j, true : false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j, true : false; }

constexpr int nax = 1e6;
int trie[nax][26];
bool is_longest[nax];
int ending[nax];
string ans;
int par[nax];
int depth[nax];
void dfs(int x) {
    while(ending[x]--) {
        ans+="P";
    }
    for (int i=0;i<26;i++) {
        if (!trie[x][i]||is_longest[trie[x][i]]) { continue; } 
        ans+=char(i+'a');
        dfs(trie[x][i]);
    }
    for (int i=0;i<26;i++) {
        if (trie[x][i]&&is_longest[trie[x][i]]) {
            ans+=char(i+'a');
            dfs(trie[x][i]);
        }
    }
    if (!is_longest[x]) {
        ans+="-";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt=1;
    par[0]=-1;
    while(n--) {
        string s;
        cin >> s;
        int x=0;
        for (auto &c: s) {
            if (!trie[x][c-'a']) { 
                trie[x][c-'a']=cnt;
                par[cnt]=x;
                depth[cnt]=depth[x]+1;
                cnt++;
            }
            x=trie[x][c-'a'];
        }
        ending[x]++;
    }
    int x=(int)(max_element(depth,depth+nax)-depth);
    while(x != -1) {
        is_longest[x]=true;
        x=par[x];
    }
    dfs(0);
    cout << ans.size() << "\n";
    for (auto &c: ans) {
        cout << c << "\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 4 ms 7004 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9304 KB Output is correct
2 Correct 15 ms 14684 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15600 KB Output is correct
2 Correct 8 ms 8024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 30224 KB Output is correct
2 Correct 72 ms 52740 KB Output is correct
3 Correct 44 ms 33264 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24312 KB Output is correct
2 Correct 88 ms 60168 KB Output is correct
3 Correct 46 ms 36500 KB Output is correct
4 Correct 75 ms 58016 KB Output is correct