oj.uz

Submission #918952

# Submission time Handle Problem Language Result Execution time Memory
918952 2024-01-30T22:07:45 Z biank Type Printer (IOI08_printer) C++14
100 / 100
 89 ms 51064 KB 
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
typedef long long ll;
typedef vector<int> vi;

const int MAXN = 5e5+5;

int adj[MAXN][26], t=0;
bool flag1[MAXN], flag2[MAXN];

void insert(string s, bool longest) {
    int u=0;
    for(char c:s) {
        flag2[u]|=longest;
        int &v=adj[u][c-'a'];
        if(!v) v=++t;
        u=v;
    }
    flag1[u]=true, flag2[u]|=longest;
}

string ans = "";

void dfs(int u) {
    if(flag1[u]) ans+='P';
    int j=-1;
    forn(i,26) {
        int v=adj[u][i];
        if(!v) continue;
        if(flag2[v]) j=i;
        else {
            ans+=char('a'+i);
            dfs(v);
        }
    }
    if(j!=-1) {
        ans+=char('a'+j);
        dfs(adj[u][j]);
    }
    if(!flag2[u]) ans+='-';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    vector<string> word(n);
    int j=0;
    forn(i,n) {
        cin >> word[i];
        if(SIZE(word[j])<SIZE(word[i])) j=i;
    }
    forn(i,n) insert(word[i], i==j);
    
    dfs(0);
    cout << SIZE(ans) << '\n';
    forn(i,SIZE(ans)) cout << ans[i] << '\n';
    
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3416 KB Output is correct
2 Correct 10 ms 6748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7916 KB Output is correct
2 Correct 5 ms 2648 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 19180 KB Output is correct
2 Correct 71 ms 43276 KB Output is correct
3 Correct 41 ms 23472 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15088 KB Output is correct
2 Correct 89 ms 51064 KB Output is correct
3 Correct 44 ms 26348 KB Output is correct
4 Correct 69 ms 48392 KB Output is correct