# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
542530 |
2022-03-26T21:08:49 Z |
Olympia |
Savez (COCI15_savez) |
C++17 |
|
1000 ms |
21296 KB |
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <limits.h>
using namespace std;
int64_t binPow (int64_t x, int64_t y, int64_t MOD) {
int64_t res = x;
int64_t ans = 1;
while (y > 0) {
if (y & 1) {
ans *= res, ans %= MOD;
}
res *= res, res %= MOD;
y /= 2;
}
return ans;
}
int64_t inv (int64_t x, int64_t MOD) {
return binPow(x, MOD - 2, MOD);
}
struct Hasher {
void resz (int mod, int base, string str) {
int n = str.size();
this->sz = n;
this->MOD = mod, this->BASE = base;
this->pref.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
pref[i] = (pref[i - 1] + (binPow(base, n - i, MOD) * (str[i - 1] - 'A' + 1)) % MOD) % MOD;
pref[i] %= MOD;
}
}
int sz;
int MOD;
int BASE;
vector<int64_t> pref;
int64_t query (int l, int r) {
return (binPow(BASE, MOD - sz + r + 1, MOD) * (pref[r + 1] - pref[l] + MOD) % MOD) % MOD;
}
};
vector<int> dp;
vector<vector<int>> adj;
int myMax = 0;
void rec (int curNode) {
if (dp[curNode] != 0) {
return;
}
dp[curNode] = 0;
for (int i: adj[curNode]) {
rec(i);
dp[curNode] = max(dp[curNode], dp[i]);
}
dp[curNode] ++;
myMax = max(myMax, dp[curNode]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
unordered_map<int64_t,int> myMap;
adj.resize(N);
dp.assign(N, 0);
for (int i = 0; i < N; i++) {
string str;
cin >> str;
Hasher h1; h1.resz(1e9 + 9, 31, str);
for (int l = 1; l <= str.size(); l++) {
if (h1.query(0, l - 1) == h1.query(str.size() - l, str.size() - 1)) {
if (myMap.count(h1.query(0, l - 1))) {
adj[i].push_back(myMap[h1.query(0, l - 1)]);
}
}
}
myMap[h1.query(0, str.size() - 1)] = i;
}
for (int i = 0; i < N; i++) {
rec(i);
}
cout << myMax;
}
Compilation message
savez.cpp: In function 'int main()':
savez.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int l = 1; l <= str.size(); l++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
77 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
962 ms |
476 KB |
Output is correct |
2 |
Correct |
978 ms |
476 KB |
Output is correct |
3 |
Execution timed out |
1030 ms |
884 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
340 KB |
Output is correct |
2 |
Correct |
961 ms |
740 KB |
Output is correct |
3 |
Correct |
991 ms |
756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1037 ms |
1936 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
3800 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
4692 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1095 ms |
5732 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1085 ms |
14376 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1072 ms |
21296 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |