| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 546573 |
2022-04-07T20:37:21 Z |
Olympia |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
17248 KB |
#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <string>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int MOD = 1e9 + 9;
const int BASE = 293;
const int inv = 706484648;
class Tree {
public:
vector<int> sub, depth, parent;
vector<int64_t> dp1, dp2;
vector<bool> hasVisited;
vector<vector<int>> adj;
vector<int64_t> powr, ipowr;
vector<vector<int>> dp;
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, int64_t val1, int64_t val2) {
dp1[curNode] = val1 = (BASE * val1 + s[curNode]) % MOD;
dp2[curNode] = val2 = (powr[d] * s[curNode] + val2) % MOD;
fine += (dp1[curNode] == dp2[curNode] && d + 1 == max_len);
dp[curNode][0] = prevNode;
for (int i = 1; i < 32; 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) {
if (d == 0) {
return l;
}
int lg2 = log2(d);
return go_up(dp[l][lg2], d - (1 << lg2));
}
int centroid;
int64_t get (int l, int r) {
if (l == centroid) {
return dp1[r];
} else if (r == centroid) {
return dp2[l];
}
if (depth[l] == depth[r]) {
return s[l];
}
if (depth[l] < depth[r]) {
return (dp1[r] - (powr[depth[r] - depth[l] + 1] * dp1[parent[l]]) % MOD + MOD) % MOD;
} else {
return (((dp2[l] - dp2[parent[r]] + MOD) % MOD) * (ipowr[depth[r]])) % MOD;
}
}
map<int,int> m1, v1;
void dfs (int curNode, int prevNode) {
if (depth[curNode] + 1 >= max_len) {
return;
}
m1[dp1[curNode]]++, v1[dp1[curNode]]++;
if (2 * depth[curNode] + 1 >= max_len) {
if (dp1[go_up(curNode, max_len - depth[curNode] - 1)] == dp2[go_up(curNode, max_len - depth[curNode] - 1)]) {
int64_t get_val = get(go_up(curNode, max_len - depth[curNode] - 2), curNode) + powr[max_len - depth[curNode] - 1] * s[centroid];
get_val %= MOD;
fine += (m1[get_val] - v1[get_val]);
}
}
for (int i: adj[curNode]) {
if (i != prevNode && !hasVisited[i]) {
dfs (i, curNode);
}
}
}
void solve (int curNode) {
dfs1(curNode, curNode);
centroid = get_centroid(curNode, curNode);
hasVisited[centroid] = true;
depth[centroid] = 0;
dp[centroid].assign(dp[centroid].size(), 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]) {
v1.clear();
dfs (i, centroid);
}
}
reverse(adj[centroid].begin(), adj[centroid].end());
m1.clear();
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
v1.clear();
dfs (i, centroid);
}
}
for (int i: adj[centroid]) {
if (!hasVisited[i]) {
solve(i);
}
}
}
Tree (int n) {
sub.resize(n), adj.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), dp.assign(n, (vector<int>)(32));
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("inp.txt", "r", stdin);
//freopen("o")
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';
}
Compilation message
lampice.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
17 | #pragma GCC optimization ("O3")
|
lampice.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
18 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
468 KB |
Output is correct |
| 2 |
Correct |
35 ms |
468 KB |
Output is correct |
| 3 |
Correct |
125 ms |
824 KB |
Output is correct |
| 4 |
Correct |
169 ms |
948 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5042 ms |
16864 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5018 ms |
17248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
468 KB |
Output is correct |
| 2 |
Correct |
35 ms |
468 KB |
Output is correct |
| 3 |
Correct |
125 ms |
824 KB |
Output is correct |
| 4 |
Correct |
169 ms |
948 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Execution timed out |
5042 ms |
16864 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
