oj.uz

Submission #1083464

# Submission time Handle Problem Language Result Execution time Memory
1083464 2024-09-03T08:48:27 Z raul2008487 Type Printer (IOI08_printer) C++17
100 / 100
 106 ms 106580 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 = 5e5 + 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 3 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 5 ms 10076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13656 KB Output is correct
2 Correct 16 ms 20056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22360 KB Output is correct
2 Correct 9 ms 11100 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 43868 KB Output is correct
2 Correct 87 ms 90688 KB Output is correct
3 Correct 50 ms 50768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35920 KB Output is correct
2 Correct 103 ms 106580 KB Output is correct
3 Correct 53 ms 56404 KB Output is correct
4 Correct 106 ms 100996 KB Output is correct