# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497212 | julian33 | Rima (COCI17_rima) | C++14 | 1100 ms | 52460 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=3e6+5; //make sure this is right
const int mod=1e9+7;
const int mod2=988244353;
const int b=131;
/*
lets denote a string by its identity
{hash of 1->n-1, full hash, len(s)} -> {x,y,l}
all strings with same x can be considered as part of same component
dp[y] = dp[x] + sz(x)
*/
struct H {
typedef uint64_t ull;
ull x; H(ull x=0) : x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
H operator-(H o) { return *this + ~o.x; }
ull get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)
struct HashInterval {
vector<H> ha, pw;
HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
pw[0] = 1;
for(int i=1;i<=sz(str);i++)
ha[i] = ha[i-1] * C + str[i-1],
pw[i] = pw[i-1] * C;
}
H hashInterval(int a, int b) { // hash [a, b)
return ha[b] - ha[a] * pw[b - a];
}
};
struct identity{
H x,y;
int l;
bool operator<(const identity &o) const{
return l<o.l;
}
};
map<H,int> dp,cnt;
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n; cin>>n;
vector<identity> all;
for(int i=0;i<n;i++){
string s; cin>>s;
reverse(s.begin(),s.end());
identity cur;
HashInterval h(s);
cur.x=h.hashInterval(0,sz(s)-1);
cur.y=h.hashInterval(0,sz(s));
cnt[cur.x]++;
cur.l=sz(s);
all.pb(cur);
}
sort(all.begin(),all.end());
int ans=0;
for(auto &[x,y,l]:all){
if(!dp.count(x)) dp[y]=cnt[x];
else dp[y]=dp[x]+cnt[x];
maxa(ans,dp[y]);
}
cout<<ans<<"\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |