oj.uz

Submission #53704

# Submission time Handle Problem Language Result Execution time Memory
53704 2018-07-01T05:04:48 Z 노영훈(#1436) Type Printer (IOI08_printer) C++11
100 / 100
 183 ms 56448 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n;
struct node {
    bool end;
    char now;
    int nxt[30]; // 'a' ~ 'z'
} trie[MX]; // root : 1
int bck=1;

void put(char S[]){
    int v=1;
    for(int i=1; S[i]!=0; i++){
        node &nd=trie[v];
        int &nxt=nd.nxt[S[i]-'a'];
        if(nxt==0){
            nxt=++bck;
        }
        v=nxt;
        trie[v].now=S[i];
    }
    trie[v].end=true;
}

int init(int v){
    node &nd=trie[v];
    int deep=0, mx=-1;
    for(int i=0; i<='z'-'a'; i++){
        int x=nd.nxt[i];
        if(x==0) continue;
        int now=init(x);
        if(deep<now+1) deep=now+1, mx=i;
    }
    if(mx>=0) swap(nd.nxt['z'-'a'], nd.nxt[mx]);
    return deep;
}

deque<char> ans;
void solve(int v){
    node &nd=trie[v];
    if(v!=1) ans.push_back(nd.now);
    if(nd.end)
        ans.push_back('P');
    for(int i=0; i<='z'-'a'; i++)
        if(nd.nxt[i]!=0)
            solve(nd.nxt[i]);
    if(v!=1) ans.push_back('-');
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    char S[30];
    for(int i=1; i<=n; i++){
        cin>>(S+1);
        put(S);
    }

    init(1);
    solve(1);
    while(!ans.empty() && ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<'\n';
    for(char c:ans) cout<<c<<'\n';

    /*
    deque<char> R[30];
    for(int i=0; i<='z'-'a'; i++){
        int v=trie[1].nxt[i];
        if(v==0) continue;
        solve(v, R[i]);
    }

    int last=-1, mx=-1, sum=0;
    for(int i=0; i<='z'-'a'; i++){
        int now=0;
        for(int j=(int)R[i].size()-1; j>=0; j--){
            if(R[i][j]!='-') break;
            now++;
        }
        if(mx<now) last=i, mx=now;
    }

    while(!R[last].empty() && R[last].back()=='-') R[last].pop_back();
    for(int i=0; i<='z'-'a'; i++)
        sum+=R[i].size();

    cout<<sum<<'\n';
    for(int i=0; i<='z'-'a'; i++){
        if(i==last) continue;
        for(char c:R[i]) cout<<c<<'\n';
    }
    for(char c:R[last]) cout<<c<<'\n';
    */
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3700 KB Output is correct
2 Correct 19 ms 7544 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8716 KB Output is correct
2 Correct 11 ms 8716 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 21020 KB Output is correct
2 Correct 183 ms 47532 KB Output is correct
3 Correct 69 ms 47532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 47532 KB Output is correct
2 Correct 154 ms 56448 KB Output is correct
3 Correct 80 ms 56448 KB Output is correct
4 Correct 166 ms 56448 KB Output is correct