oj.uz

Submission #953206

# Submission time Handle Problem Language Result Execution time Memory
953206 2024-03-25T17:17:57 Z AverageAmogusEnjoyer Type Printer (IOI08_printer) C++17
90 / 100
 77 ms 93012 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 = 4e5;
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 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4444 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7260 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11760 KB Output is correct
2 Correct 6 ms 6236 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 22264 KB Output is correct
2 Correct 77 ms 45072 KB Output is correct
3 Correct 39 ms 25584 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18424 KB Output is correct
2 Runtime error 68 ms 93012 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -