oj.uz

Submission #165411

# Submission time Handle Problem Language Result Execution time Memory
165411 2019-11-27T06:53:57 Z egekabas Savez (COCI15_savez) C++14
120 / 120
 972 ms 13560 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n;
ll lps[100009];
map<string, ll> dp;
void func(string s){
    int len = 0;
    int i = 1;
    while(i < s.size()){
        if(s[i] == s[len]){
            ++len;
            lps[i] = len;
            ++i;
        }
        else if(len > 0)
            len = lps[len-1];
        else{
            lps[i] = 0;
            ++i;
        }
    }
}
int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    ll ans = 0;
    for(ll i = 0; i < n; ++i){
        string s;
        cin >> s;
        func(s);
        ll cur = 1+dp[s];
        ll len = lps[s.size()-1];
        while(len > 0){
            cur = max(cur, 1+dp[s.substr(0, len)]);
            len = lps[len-1];
        }
        dp[s] = cur;
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

Compilation message

savez.cpp: In function 'void func(std::__cxx11::string)':
savez.cpp:20:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < s.size()){
           ~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 3688 KB Output is correct
2 Correct 932 ms 3804 KB Output is correct
3 Correct 972 ms 3960 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 391 ms 6544 KB Output is correct
3 Correct 670 ms 13560 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1372 KB Output is correct
2 Correct 142 ms 1400 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1412 KB Output is correct
2 Correct 111 ms 1272 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1396 KB Output is correct
2 Correct 100 ms 1404 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1496 KB Output is correct
2 Correct 111 ms 1568 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 1568 KB Output is correct
2 Correct 133 ms 1524 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1784 KB Output is correct
2 Correct 175 ms 1804 KB Output is correct
3 Correct 292 ms 2296 KB Output is correct