oj.uz

Submission #114659

# Submission time Handle Problem Language Result Execution time Memory
114659 2019-06-02T07:57:45 Z zubec Type Printer (IOI08_printer) C++14
100 / 100
 205 ms 58716 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int n;

struct trie{
    int term;
    int nxt[26];
};

trie t[500100];

int tin[500100], tout[500100], pr[500100], tim, mxdeep[500100];

int kol = 0;

void dfs(int v, int deep){
    tin[v] = ++tim;
    mxdeep[v] = deep;
    for (int i = 0; i < 26; i++){
        if (t[v].nxt[i] != 0){
            pr[t[v].nxt[i]] = v;
            dfs(t[v].nxt[i], deep+1);
            mxdeep[v] = max(mxdeep[v], mxdeep[t[v].nxt[i]]);
        }
    }

    tout[v] = tim;
}

bool cmp(int a, int b){
    return mxdeep[a] < mxdeep[b];
}

bool ifpred(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lst = -1;

int deep = 0;

string s[25100];

vector <char> ansvec;

void dfs2(int v){
    if (t[v].term){
        int id = t[v].term;
        if (lst == -1){
            for (int j = 0; j < s[id].size(); j++){
                ansvec.push_back(s[id][j]);
            }
            deep = s[id].size();
            lst = v;
        } else {
            while(!ifpred(lst, v)){
                lst = pr[lst];
                --deep;
                ansvec.push_back('-');
            }
            while(deep < s[id].size()){
                ansvec.push_back(s[id][deep]);
                ++deep;
            }
            lst = v;
        }
        ansvec.push_back('P');
    }
    vector <int> vec;
    for (int i = 0; i < 26; i++){
        if (t[v].nxt[i] != 0){
            vec.push_back(t[v].nxt[i]);
        }
    }
    sort(vec.begin(), vec.end(), cmp);
    for (int i = 0; i < vec.size(); i++)
        dfs2(vec[i]);
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        string s;
        cin >> s;
        int v = 0;
        for (int j = 0; j < s.size(); j++){
            if (t[v].nxt[s[j]-'a'] == 0){
                t[v].nxt[s[j]-'a'] = ++kol;
            }
            v = t[v].nxt[s[j]-'a'];
        }
        t[v].term = i;
        ::s[i] = s;
    }
    dfs(0, 0);
    dfs2(0);

    cout << ansvec.size() << "\n";
    for (int i = 0; i < ansvec.size(); i++)
        cout << ansvec[i] << "\n";

}

Compilation message

printer.cpp: In function 'void dfs2(int)':
printer.cpp:53:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < s[id].size(); j++){
                             ~~^~~~~~~~~~~~~~
printer.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(deep < s[id].size()){
                   ~~~~~^~~~~~~~~~~~~~
printer.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.size(); j++){
                         ~~^~~~~~~~~~
printer.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ansvec.size(); i++)
                     ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4352 KB Output is correct
2 Correct 29 ms 8220 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9336 KB Output is correct
2 Correct 13 ms 3064 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21960 KB Output is correct
2 Correct 176 ms 49516 KB Output is correct
3 Correct 91 ms 26740 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17140 KB Output is correct
2 Correct 205 ms 58716 KB Output is correct
3 Correct 110 ms 30068 KB Output is correct
4 Correct 162 ms 55536 KB Output is correct