Submission #59349

#TimeUsernameProblemLanguageResultExecution timeMemory
59349BenqSavez (COCI15_savez)C++14
120 / 120
96 ms20804 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 2000001; vector<map<pair<char,char>,int>> tri; int bes[MX]; int nex = 1, ans; void ins(string t) { int cur = 0, res = 0; F0R(i,sz(t)) { pair<char,char> p = {t[i],t[sz(t)-1-i]}; if (!tri[cur].count(p)) { tri[cur][p] = nex ++; tri.pb(map<pair<char,char>,int>()); } cur = tri[cur][p]; res = max(res,bes[cur]); } ans = max(ans,bes[cur] = res+1); } int N; int main() { ios_base::sync_with_stdio(0); cin.tie(0); tri.pb(map<pair<char,char>,int>()); cin >> N; F0R(i,N) { string s; cin >> s; ins(s); } cout << ans; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...