oj.uz

Submission #588512

# Submission time Handle Problem Language Result Execution time Memory
588512 2022-07-03T12:35:45 Z Odavey Type Printer (IOI08_printer) C++14
90 / 100
 1000 ms 55292 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            500001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

static const int ALPH_SIZE = 27;

int glit = 0;

int desc[MX_N];
char val[MX_N];
int edge[MX_N][ALPH_SIZE];
bool last[MX_N];

int ans;

int create(char v){
    ans = glit++;
    for(int i=0;i<ALPH_SIZE;++i)
        edge[ans][i] = -1;
    val[ans] = v;
    last[ans] = 0;
    desc[ans] = 0;
    return ans;
}

string ins;
vector<char> outp;
int root;

void insert(int at, int pos){
    if(pos == ins.size()){
        desc[at] = 0;
        return;
    }
    if(edge[at][ins[pos] - (int)'a'] == -1){
        edge[at][ins[pos] - (int)'a'] = create(ins[pos]);
    }
    insert(edge[at][ins[pos] - (int)'a'], pos+1);
    desc[at] = max(desc[at], 1+desc[edge[at][ins[pos] - (int)'a']]);
}

int maxdesc;
int best;

void getlast(int at){
    last[at] = 1;
    maxdesc = -1;
    best = -1;
    for(int i=0;i<ALPH_SIZE;++i){
        if(edge[at][i] == -1){
            continue;
        }
        if(maxdesc < desc[edge[at][i]]){
            best = edge[at][i];
            maxdesc = desc[edge[at][i]];
        }
    }
    if(maxdesc == -1)
        return;
    getlast(best);
}


void PrintGraph(int at){
    if(at != root){
        if(val[at] == ('z' + 1))
            outp.pb('P');
        else
            outp.pb(val[at]);
    }
    int L = -1;
    for(int i=0;i<ALPH_SIZE;++i){
        if(edge[at][i] == -1){
            continue;
        }
        if(last[edge[at][i]]){
            L = edge[at][i];
            continue;
        }
        PrintGraph(edge[at][i]);
    }
    if(L != -1){
        PrintGraph(L);
    }
    if(val[at] == ('z' + 1) || last[at] || at == root){
        return;
    }
    outp.pb('-');
}

int main(){
    FastIO;
    int n;
    cin >> n;
    root = create('R');
    for(int i=0;i<n;++i){
        cin >> ins;
        ins += ('z' + 1);
        insert(root, 0);
    }
    getlast(root);
    PrintGraph(root);
    cout << outp.size() << endl;
    for(char& c : outp)
        cout << c << endl;
}

Compilation message

printer.cpp: In function 'void insert(int, int)':
printer.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(pos == ins.size()){
      |        ~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 9 ms 844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1364 KB Output is correct
2 Correct 29 ms 1492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3704 KB Output is correct
2 Correct 130 ms 7476 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9004 KB Output is correct
2 Correct 46 ms 3376 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 21464 KB Output is correct
2 Correct 871 ms 46504 KB Output is correct
3 Correct 455 ms 25452 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 18132 KB Output is correct
2 Execution timed out 1062 ms 55292 KB Time limit exceeded
3 Halted 0 ms 0 KB -