| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 546628 |
2022-04-07T22:27:57 Z |
Olympia |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
11912 KB |
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <unordered_set>
#include <string>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
using namespace std;
const int MOD = 1e9 + 9;
const int M = 1e9 + 9;
const int BASE = 293;
const int inv = 706484648;
struct modint {
modint() : n(0) {}
template <class T> modint(T n) { n %= M; if (n < 0) n += M; this->n = n; }
modint & operator+=(const modint &r) { n += r.n; if (n >= M) n -= M; return *this; }
modint & operator-=(const modint &r) { n -= r.n; if (n < 0) n += M; return *this; }
modint & operator*=(const modint &r) { n = (int) ((long long) n * r.n % M); return *this; }
modint & operator--() { if (--n == -1) n = M - 1; return *this; }
modint & operator++() { if (++n == M) n = 0; return *this; }
modint operator--(int) { modint t = *this; --*this; return t; }
modint operator++(int) { modint t = *this; ++*this; return t; }
modint operator-() const { return 0 - *this; }
modint operator+() const { return *this; }
modint pow(long long k = M - 2) const {
modint f = *this, p = 1;
while (k > 0) {
if (k % 2 == 1) f *= p;
p *= p, k /= 2;
}
return f;
}
int mod() const { return M; }
friend modint operator+(modint l, const modint &r) { return l += r; }
friend modint operator-(modint l, const modint &r) { return l -= r; }
friend modint operator*(modint l, const modint &r) { return l *= r; }
friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }
friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }
friend ostream & operator<<(ostream &out, const modint &r) { return out << r.n; }
int n;
};
class Tree {
public:
vector<int> sub, depth, parent;
vector<modint> dp1, dp2;
vector<bool> hasVisited;
vector<int> adj[(int)5e4];
vector<int64_t> powr, ipowr;
int dp[(int)5e4][17];
string s;
int sz;
int dfs1 (int curNode, int prevNode) {
sub[curNode] = 1;
for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode) sub[curNode] += dfs1(i, curNode);
return (sz = sub[curNode]);
}
int get_centroid (int curNode, int prevNode) {
for (int i: adj[curNode]) if (!hasVisited[i] && i != prevNode && sub[i] > sz/2) return get_centroid(i, curNode);
return curNode;
}
int max_len; int fine = 0;
void fill (int curNode, int prevNode, int d, modint val1, modint val2) {
dp1[curNode] = val1 = BASE * val1 + s[curNode];
dp2[curNode] = val2 = powr[d] * s[curNode] + val2;
fine += (dp1[curNode] == dp2[curNode] && d + 1 == max_len);
dp[curNode][0] = prevNode;
for (int i = 1; i < 17; i++) {
dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1];
}
depth[curNode] = d;
parent[curNode] = prevNode;
for (int i: adj[curNode]) {
if (!hasVisited[i] && i != prevNode) {
fill(i, curNode, d + 1, val1, val2);
}
}
}
int64_t go_up (int l, int d) {
while (d) {
l = dp[l][(int)log2(d & -d)];
d -= (d & -d);
}
return l;
}
int centroid;
int64_t get (int l, int r) {
if (depth[l] < depth[r]) {
return (dp1[r] - (powr[depth[r] - depth[l] + 1] * dp1[parent[l]])).n;
} else {
return ((dp2[l] - dp2[parent[r]]) * (ipowr[depth[r]])).n;
}
}
unordered_set<int> m1;
vector<int> to_do;
void dfs (int curNode, int prevNode) {
if (depth[curNode] + 1 >= max_len) {
return;
}
to_do.push_back(dp1[curNode].n);
if (2 * depth[curNode] + 1 >= max_len) {
int x = go_up(curNode, max_len - depth[curNode] - 2);
if (dp1[parent[x]] == dp2[parent[x]]) {
if (m1.count((get(x, curNode) + powr[max_len - depth[curNode] - 1] * s[centroid]) % MOD)) {
fine ++;
return;
}
}
}
for (int i: adj[curNode]) {
if (i != prevNode && !hasVisited[i]) {
dfs (i, curNode);
}
}
}
bool solve (int curNode) {
dfs1(curNode, curNode);
centroid = get_centroid(curNode, curNode);
hasVisited[centroid] = true;
depth[centroid] = 0;
for (int i = 0; i < 17; i++) dp[centroid][i] = centroid;
dp1[centroid] = s[centroid], dp2[centroid] = s[centroid];
fine += (max_len == 1);
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
fill(i, centroid, 1, s[centroid], s[centroid]);
}
}
m1.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
dfs (i, centroid);
for (int j: to_do) m1.insert(j);
to_do.clear();
}
}
if (fine) return true;
reverse(adj[centroid].begin(), adj[centroid].end());
m1.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
dfs (i, centroid);
for (int j: to_do) m1.insert(j);
to_do.clear();
}
}
if (fine) return true;
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
if (solve(i)) {
return true;
}
}
}
return false;
}
Tree (int n) {
sub.resize(n), hasVisited.assign(n, false); powr.push_back(1); for (int i = 0; i <= n + 5; i++) powr.push_back(powr.back() * BASE), powr.back() %= MOD;
ipowr.push_back(1); for (int i = 0; i <= n + 5; i++) ipowr.push_back(ipowr.back() * inv), powr.back() %= MOD;
parent.resize(n), depth.resize(n), dp1.resize(n), dp2.resize(n);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
string s; cin >> s;
Tree myTree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
myTree.adj[u].push_back(v), myTree.adj[v].push_back(u);
}
myTree.s = s;
int myMax = 0;
int l = 0;
int r = s.length()/2;
while (l != r) {
int m = (l + r + 1)/2;
myTree.max_len = 2 * m; myTree.fine = 0; myTree.hasVisited.assign(n, false);
myTree.solve(0);
if (myTree.fine) {
l = m;
} else {
r = m - 1;
}
}
myMax = max(myMax, 2 * l);
l = 0;
r = s.length()/2;
while (l != r) {
int m = (l + r + 1)/2;
myTree.max_len = 2 * m + 1; myTree.fine = 0; myTree.hasVisited.assign(n, false);
myTree.solve(0);
if (myTree.fine) {
l = m;
} else {
r = m - 1;
}
}
myMax = max(myMax, 2 * l + 1);
cout << myMax;
//cout << inv(BASE) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
54 ms |
5004 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5030 ms |
11912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
11216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
54 ms |
5004 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4692 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 8 |
Execution timed out |
5030 ms |
11912 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
