oj.uz

Submission #1083461

# Submission time Handle Problem Language Result Execution time Memory
1083461 2024-09-03T08:46:01 Z raul2008487 Type Printer (IOI08_printer) C++17
80 / 100
 36 ms 48216 KB 
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define endl "\n"
#define vl vector<ll>
#define all(v) v.begin(), v.end()

using namespace std;
const ll inf = 1e17;
const int sz = 1e5 + 123;
const int MAX = 2001;
const ll mod = 1e9;
ll id, to[sz][26], par[sz], d[sz], noe;
vl cnt(sz), sub(sz);
char alphabet[26];
bool longest[sz];
array<ll, 2> best = {0, 0};
void insert(string &s){
    ll p = 0;
    sub[0] ++;
    for(auto c: s){
        if(!to[p][c - 'a']){
            to[p][c - 'a'] = ++id;
            par[id] = p;
            d[id] = d[p] + 1;
            if(d[id] > best[0]){
                best = {d[id], id};
            }
        }
        p = to[p][c - 'a'];
        sub[p] ++;
    }
    cnt[p] ++;
}
void dfs(ll p){
    while(cnt[p]--){
        cout << 'P' << endl;
    }
    char l = '*';
    ll nxt;
    for(char c: alphabet){
        nxt = to[p][c - 'a'];
        if(!nxt){continue;}
        if(longest[nxt]){
            l = c;
        }
        else{
            cout << c << endl;
            dfs(nxt);
            cout << '-' << endl;
        }
    }
    if(l != '*'){
        cout << l << endl;
        dfs(to[p][l - 'a']);
    }
}
void solve(){
    ll n, i, j;
    for(i = 0; i < 26; i++){
        alphabet[i] = char('a' + i);
    }
    cin >> n;
    string s;
    for(i = 1; i <= n; i++){
        cin >> s;
        insert(s);
    }
    ll node = best[1];
    noe  = id * 2;
    // cout << noe << endl;
    while(node){
        longest[node] = 1;
        noe --;
        node = par[node];
    }
    cout << noe + n << endl;
    dfs(0);


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
/*
5
pushkin
lermontov
tolstoy
gogol
gorkiy
*/

Compilation message

printer.cpp: In function 'void solve()':
printer.cpp:63:14: warning: unused variable 'j' [-Wunused-variable]
   63 |     ll n, i, j;
      |              ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7516 KB Output is correct
2 Correct 12 ms 13912 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 48216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 48084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -