oj.uz

Submission #122190

# Submission time Handle Problem Language Result Execution time Memory
122190 2019-06-27T19:42:03 Z thebes Type Printer (IOI08_printer) C++14
100 / 100
 170 ms 51692 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 3e4+4, MM = 5e5+5;
string s;
vector<char> mv;
int n, i, t[MM][26], lol[MM], len[MM], nxt, p;
int solve(int p){
    int mx=0, nx=-1, r;
    for(int i=0;i<26;i++){
        if(!t[p][i]) continue;
        if(len[t[p][i]]>mx){
            mx = len[t[p][i]];
            nx = i;
        }
    }
    if(lol[p]) mv.push_back('P');
    if(nx==-1) return 0;
    for(int i=0;i<26;i++){
        if(!t[p][i]||i==nx) continue;
        mv.push_back(i+'a');
        r = solve(t[p][i])+1;
        while(r--) mv.push_back('-');
    }
    mv.push_back('a'+nx);
    r=solve(t[p][nx])+1;
    return r;
}
int main(){
    for(scanf("%d",&n),i=1;i<=n;i++){
        cin >> s; p = 0;
        for(auto c : s){
            if(!t[p][c-'a']) t[p][c-'a']=++nxt;
            p = t[p][c-'a'];
            len[p] = max(len[p], (int)s.size());
        }
        lol[p] = 1;
    }
    solve(0);
    printf("%d\n",mv.size());
    for(auto v : mv) printf("%c\n",v);
    return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:40:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",mv.size());
                   ~~~~~~~~~^
printer.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d",&n),i=1;i<=n;i++){
         ~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3200 KB Output is correct
2 Correct 21 ms 6776 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7796 KB Output is correct
2 Correct 14 ms 2176 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 19184 KB Output is correct
2 Correct 139 ms 43500 KB Output is correct
3 Correct 84 ms 22840 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15088 KB Output is correct
2 Correct 170 ms 51692 KB Output is correct
3 Correct 99 ms 25712 KB Output is correct
4 Correct 138 ms 48748 KB Output is correct