Submission #743675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743675	2023-05-17T16:56:33 Z	vjudge1	Rima (COCI17_rima)	C++17	14 / 140	284 ms	125612 KB

rima

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 5, M = 3e6 + 6, mod = 998244353;
const int K = 26;
int dp[M];

struct Vertex {
    int next[K];

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};


vector<Vertex> t(1);

pair<int, int> add_string(string const &s) {
    int v = 0, curDep = 0;
    int parent = 0;
    for (char ch: s) {
        int c = ch - 'a';
        if (t[v].next[c] == -1) {
            t[v].next[c] = t.size();
            t.emplace_back();
        }
        parent = v;
        v = t[v].next[c];
    }
    return {v, parent};
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        reverse(v[i].begin(), v[i].end());
        pair<int, int> p = add_string(v[i]);
        int idx = p.first;
        int par = p.second;
        int mx = 0;
        for (int j = 0; j < K; ++j) { // me with same size equal me
            if (t[par].next[j] != -1) {
                mx = max(mx, dp[t[par].next[j]] + 1);
            }
        }
        mx = max(mx, dp[par] + 1);// me with size less than me by 1
        for (int j = 0; j < K; ++j) { // me with size greater than me by 1
            if (t[idx].next[j] != -1) {
                mx = max(mx, dp[t[idx].next[j]] + 1);
            }
        }
        dp[idx] = mx;
    }
    cout << *max_element(dp, dp + M) << '\n';
}

Compilation message

rima.cpp: In function 'std::pair<int, int> add_string(const string&)':
rima.cpp:23:16: warning: unused variable 'curDep' [-Wunused-variable]
   23 |     int v = 0, curDep = 0;
      |                ^~~~~~

Subtask #1

14.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	340 KB	Output isn't correct
2	Correct	5 ms	328 KB	Output is correct
3	Incorrect	5 ms	432 KB	Output isn't correct
4	Incorrect	284 ms	125612 KB	Output isn't correct
5	Incorrect	29 ms	4420 KB	Output isn't correct
6	Incorrect	52 ms	54832 KB	Output isn't correct
7	Incorrect	58 ms	54840 KB	Output isn't correct
8	Incorrect	52 ms	54624 KB	Output isn't correct
9	Incorrect	72 ms	57000 KB	Output isn't correct
10	Incorrect	47 ms	54656 KB	Output isn't correct