oj.uz

Submission #114658

# Submission time Handle Problem Language Result Execution time Memory
114658 2019-06-02T07:57:24 Z zubec Type Printer (IOI08_printer) C++14
0 / 100
 115 ms 22556 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;
        cout << "kek " << v << ' ' << s[id] << endl;
        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:54:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < s[id].size(); j++){
                             ~~^~~~~~~~~~~~~~
printer.cpp:65:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(deep < s[id].size()){
                   ~~~~~^~~~~~~~~~~~~~
printer.cpp:80: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:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.size(); j++){
                         ~~^~~~~~~~~~
printer.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ansvec.size(); i++)
                     ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1152 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1152 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1152 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1152 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1280 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2048 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4480 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 9720 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 22556 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 17780 KB Expected integer, but "kek" found
2 Halted 0 ms 0 KB -