oj.uz

Submission #217748

# Submission time Handle Problem Language Result Execution time Memory
217748 2020-03-30T15:25:06 Z mhy908 Type Printer (IOI08_printer) C++14
100 / 100
 198 ms 126584 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, re;
char input[30], ans[1000010];
struct TRIE{
    struct NODE{
        int pr, maxd;
        vector<int> vc;
        NODE* link[26];
        NODE(){
            pr=maxd=0;
            for(int i=0; i<26; i++)link[i]=0;
        }
    }*rt;
    TRIE(){rt=new NODE();}
    void update(NODE *nd, char str[], int lv){
        if(!str[lv]){
            nd->pr++;
            return;
        }
        nd->vc.pb(str[lv]-'a');
        if(nd->link[str[lv]-'a']==0)nd->link[str[lv]-'a']=new NODE();
        update(nd->link[str[lv]-'a'], str, lv+1);
        nd->maxd=max(nd->maxd, nd->link[str[lv]-'a']->maxd+1);
    }
    void update(char str[], int lv){update(rt, str, lv);}
    void print(NODE *nd){
        sortvec(nd->vc);
        compress(nd->vc);
        vector<pii> tmp;
        for(auto i:nd->vc)tmp.pb(mp(nd->link[i]->maxd, i));
        sortvec(tmp);
        for(int i=1; i<=nd->pr; i++)ans[++re]='P';
        for(auto i:tmp){
            ans[++re]='a'+i.S;
            print(nd->link[i.S]);
        }
        ans[++re]='-';
    }
    void print(){print(rt);}
}tr;
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        memset(input, 0, sizeof input);
        scanf("%s", input+1);
        tr.update(input, 1);
    }
    tr.print();
    while(re){
        if(ans[re]!='-')break;
        ans[re--]=0;
    }
    printf("%d\n", re);
    for(int i=1; i<=re; i++)printf("%c\n", ans[i]);
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
printer.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", input+1);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 488 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2268 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7424 KB Output is correct
2 Correct 30 ms 15744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18560 KB Output is correct
2 Correct 19 ms 4992 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 46328 KB Output is correct
2 Correct 172 ms 106360 KB Output is correct
3 Correct 94 ms 55416 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 36088 KB Output is correct
2 Correct 198 ms 126584 KB Output is correct
3 Correct 117 ms 62968 KB Output is correct
4 Correct 183 ms 119544 KB Output is correct