oj.uz

Submission #388134

# Submission time Handle Problem Language Result Execution time Memory
388134 2021-04-10T08:26:55 Z IloveN Type Printer (IOI08_printer) C++14
100 / 100
 224 ms 89912 KB 
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e5+10;

struct node
{
    map<char,node*> nxt;
    int mx_len;
    vector<pair<int,char>> order;
};

node* root=new node();

void add_string(string s)
{
    node* cur=root;
    for (char c : s)
    {
        if (cur->nxt[c]==NULL) cur->nxt[c]=new node();
        cur=cur->nxt[c];
    }
    cur->mx_len=s.length();
}

void dfs(node *cur)
{
    if (cur->nxt.empty()) return;
    cur->mx_len=0;
    vector<pair<int,char>> &vt=cur->order;
    for (pair<char,node*> p : cur->nxt)
    {
        dfs(p.se);
        cur->mx_len=max(cur->mx_len,p.se->mx_len);
        vt.eb(p.se->mx_len,p.fi);
    }
    sort(all(vt));
}

vector<char> ans;

void print(node *cur)
{
    for (pair<int,char> p : cur->order)
        if (p.se=='P') ans.eb(p.se);
        else
        {
            ans.eb(p.se);
            print(cur->nxt[p.se]);
            ans.eb('-');
        }
}

int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s+='P';
        add_string(s);
    }
    dfs(root);
    print(root);
    while (ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<"\n";
    for (char c : ans) cout<<c<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 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 0 ms 204 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 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 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 1100 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5692 KB Output is correct
2 Correct 30 ms 11776 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14272 KB Output is correct
2 Correct 25 ms 4812 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 34620 KB Output is correct
2 Correct 197 ms 75576 KB Output is correct
3 Correct 113 ms 40892 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 28860 KB Output is correct
2 Correct 224 ms 89912 KB Output is correct
3 Correct 125 ms 46524 KB Output is correct
4 Correct 182 ms 85276 KB Output is correct