oj.uz

Submission #404999

# Submission time Handle Problem Language Result Execution time Memory
404999 2021-05-15T13:45:42 Z Dremix10 Type Printer (IOI08_printer) C++17
100 / 100
 170 ms 51584 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int N = 5e5+5;

struct ano{
     int nxt[26] = {};
     bool word = false;
};

ano trie[N];
int curr = 2;

void add(string &s){
    int i = 1;
    for(auto x : s){
        int nxt = trie[i].nxt[x-'a'];
        if(!nxt){
            trie[i].nxt[x-'a'] = curr;
            nxt = curr++;
        }
        i = nxt;
    }
    trie[i].word = true;
}

int deep[N];

void dfs(int s){
    for(int i=0;i<26;i++){
        int x = trie[s].nxt[i];
        if(!x)continue;
        dfs(x);
        deep[s] = max(deep[s],deep[x]);
    }
    deep[s] ++;
}

string ans = "";

void solve(int s){
    vector<pi> go;
    for(int i=0;i<26;i++){
        int x = trie[s].nxt[i];
        if(!x)continue;
        go.push_back({deep[x],i});
    }
    sort(all(go));
    //ppv(go)
    if(trie[s].word)
        ans += 'P';
    for(auto x : go){
        ans += (char)(x.S + 'a');
        solve(trie[s].nxt[x.S]);
        ans += '-';
    }
    //p(ans)
}

int main(){
fastio

int n;
cin>>n;

int i;

for(i=0;i<n;i++){
    string s;cin>>s;
    add(s);
}

dfs(1);

/*
for(i=1;i<curr;i++){
    p2(deep[i],trie[i].word)
    for(int j=0;j<26;j++){
        if(!trie[i].nxt[j])continue;
        p2((char)(j+'a'),trie[i].nxt[j])
    }
}*/

solve(1);

while(ans.back() == '-')ans.pop_back();

cout<<sz(ans)<<endl;
for(auto x : ans)
    cout<<x<<endl;



}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3276 KB Output is correct
2 Correct 21 ms 6604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7896 KB Output is correct
2 Correct 9 ms 1988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 19104 KB Output is correct
2 Correct 147 ms 43476 KB Output is correct
3 Correct 90 ms 22628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15000 KB Output is correct
2 Correct 170 ms 51584 KB Output is correct
3 Correct 93 ms 25632 KB Output is correct
4 Correct 144 ms 48752 KB Output is correct