Submission #66397

#TimeUsernameProblemLanguageResultExecution timeMemory
66397forestryksSavez (COCI15_savez)C++14
120 / 120
177 ms57092 KiB
/////////////////////////////////////////////////////////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; // #define int long long #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout) #define f first #define s second #define x1 x1qwer #define y1 y1qwer #define right right123 #define left left123 #define foreach(it, v) for (auto it : v) #define rep(it, n) for (int it = 0; it < n; ++it) #define forin(it, l, r) for (int it = l; it < r; ++it) #define all(x) x.begin(), x.end() typedef long long ll; typedef unsigned long long ull; typedef double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double DINF = numeric_limits<double>::infinity(); const ll MOD = 1e9 + 7; const double EPS = 1e-7; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } mt19937 mmtw_(MOD); uniform_int_distribution<ll> rd_; ll randomll() { return rd_(mmtw_);} ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; } template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); } //////////////////////////////////////////////////////////////////////////////////////////////// struct MyMap : vector<pair<short, int>> { int& operator[](const short v) { auto it = lower_bound(this->begin(), this->end(), make_pair(v, -1)); if (it != this->end() && it->first == v) { return it->second; } return this->insert(it, {v, 0})->second; } }; const int MAXN = 1e6 + 5; int n; int last = 1; // map<int, int> to[MAXN]; MyMap to[MAXN]; int p[MAXN]; vector<string> s; int res[MAXN]; int get(const string &s, int i) { return (s[i] - 'A') + (s[s.size() - 1 - i] - 'A') * 26; } int trie_add(const string &s) { int n = s.size(); int v = 0; for (int i = 0; i < n; ++i) { int ch = get(s, i); if (to[v][ch] == 0) { to[v][ch] = last; p[last] = v; v = last++; } else { v = to[v][ch]; } } res[v]++; int r = res[v]; while (p[v] != -1) { res[p[v]] = max(res[p[v]], res[v]); v = p[v]; } return r; } int main() { FAST_IO; cin >> n; rep(i, n) { string a; cin >> a; s.push_back(a); } reverse(s.begin(), s.end()); p[0] = -1; int res = 0; for (int i = 0; i < n; ++i) {; res = max(res, trie_add(s[i])); } cout << res << endl; }
#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...