Submission #167794

#	Time	Username	Problem	Language	Result	Execution time	Memory
167794		egekabas	Rima (COCI17_rima)	C++14	56 / 140	386 ms	98044 KiB

rima

#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<int, int>  pii;
typedef pair<ld, ld>  pld;
int n;
string s[500009];
int edge[3000000][30];
int part[3000000];
int full[3000000];
int dp[3000000];
int cur = 2;
int ans;
int go(int root, char c){
    int tmp = (int)(c - 'a');
    if(edge[root][tmp] != 0)
        return edge[root][tmp];
    return edge[root][tmp] = cur++;
}
void add(string s){
    int root = 1;
    for(int i = 0; i < s.size(); ++i){
        root = go(root, s[i]);
        if(i == s.size()-2 || (i == 0 && s.size() == 1))
            part[root]++;
        if(i == s.size()-1)
            full[root]++;
    }
}
int f2(int root){
    if(dp[root] != 0)
        return dp[root];
    if(part[root] == 0)
        return 0;
    dp[root] += part[root];
    int maxi = 0;
    for(int i = 0; i <= 'z'-'a'; ++i){
        if(edge[root][i] != 0){
            if(full[edge[root][i]] > 0)
                maxi = max(maxi, f2(edge[root][i]));
        }
    }
    dp[root] += maxi;
    ans = max(ans, dp[root]);
    return dp[root];
}
void f1(int root){  
    f2(root);
    for(int i = 0; i <= 'z'-'a'; ++i){
        if(edge[root][i] != 0)
            f1(edge[root][i]);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
        add(s[i]);
    }
    f1(1);
    cout << ans << "\n";

}

Compilation message (stderr)

rima.cpp: In function 'void add(std::__cxx11::string)':
rima.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); ++i){
                    ~~^~~~~~~~~~
rima.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == s.size()-2 || (i == 0 && s.size() == 1))
            ~~^~~~~~~~~~~~~
rima.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == s.size()-1)
            ~~^~~~~~~~~~~~~

• Subtask 1: 56 / 140