oj.uz

Submission #396248

# Submission time Handle Problem Language Result Execution time Memory
396248 2021-04-29T15:29:58 Z Sundavar Type Printer (IOI08_printer) C++14
100 / 100
 342 ms 48616 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
    map<int,int> to;
    bool end = false;
    int depth = 0;
};
vector<node> graph;

void add(string& s){
    int curr = 0;
    for(char c : s){
        if(graph[curr].to.count(c-'a') == 0){
            graph[curr].to[c-'a'] = graph.size();
            graph.push_back(node());
        }
        curr = graph[curr].to[c-'a'];
    }
    graph[curr].end = true;
}

string sol;
int getDepth(int curr){
    int ans = -1;
    for(int i = 0; i < 26; i++)
        if(graph[curr].to.count(i) != 0)
            ans = max(ans, getDepth(graph[curr].to[i]));
    graph[curr].depth = ++ans;
    return ans;
}
void walk(int curr, string& s, string& ending){
    if(graph[curr].end)
        s += 'P';
    vector<pair<int,int> > to;
    for(int i = 0; i < 26; i++)
        if(graph[curr].to.count(i) != 0)
            to.push_back({graph[graph[curr].to[i]].depth, i});
    sort(to.begin(), to.end());
    for(pair<int,int>& t : to){
        s += ending; ending = "";
        s += (char)('a'+t.second);
        walk(graph[curr].to[t.second], s, ending);
    }
    ending += "-";
}

int main(){
    int n;
    cin>>n;
    graph.push_back(node());
    while(n--){
        string s;
        cin>>s;
        add(s);
    }
    string sol = "", ending = "";
    getDepth(0);
    walk(0, sol, ending);
    cout<<sol.size()<<"\n";
    for(char& a : sol)
        cout<<a<<"\n";

}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1000 KB Output is correct
2 Correct 9 ms 1512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3016 KB Output is correct
2 Correct 60 ms 6104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7348 KB Output is correct
2 Correct 19 ms 1720 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 20732 KB Output is correct
2 Correct 290 ms 41328 KB Output is correct
3 Correct 175 ms 21060 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 14208 KB Output is correct
2 Correct 342 ms 48616 KB Output is correct
3 Correct 178 ms 23788 KB Output is correct
4 Correct 295 ms 45880 KB Output is correct