| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1065585 |
2024-08-19T09:39:22 Z |
Flan312 |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
6580 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
#define all(s) s.begin(), s.end()
using namespace std;
const ll base = 311;
const int nmax = 5e4 + 2;
ll pw[nmax];
int n;
string a;
basic_string <int> adj[nmax];
struct Hash
{
ll hl[nmax], hr[nmax], pw[nmax];
int len;
void push_back(char c)
{
hl[len + 1] = hl[len] * base + c;
hr[len + 1] = hr[len] + c * pw[len];
++len;
}
void pop_back()
{
--len;
}
void clear()
{
len = 0;
}
bool isPalin(int l)
{
return hl[l] == hr[l];
}
ll get(int l)
{
return hl[len] - hl[len - l] * pw[l];
}
Hash()
{
len = 0;
pw[0] = 1;
for (int i = 1; i < nmax; ++i)
pw[i] = pw[i - 1] * base;
}
} hs;
struct centroidDecomposition
{
int sz[nmax], par[nmax];
bool del[nmax];
void init()
{
memset(del, 0, (n + 1) * sizeof(bool));
}
void dfs(int u, int p)
{
sz[u] = 1;
for (auto &v : adj[u])
{
if (v == p || del[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int p, int total)
{
for (auto &v : adj[u])
{
if (v == p || del[v]) continue;
if (sz[v] > (total >> 1))
return findCentroid(v, u, total);
}
return u;
}
unordered_map <ll, int> mp;
bool dfs_update(int u, int p, int depth, int len)
{
hs.push_back(a[u]);
if (depth * 2 >= len && hs.isPalin(2 * depth - len)) //duong di qua goc tu 2 dinh con cach goc 1 khoang depth
mp[hs.get(len - depth)] = 1;
if (depth == len && hs.isPalin(len))
return 1;
for (auto &v : adj[u])
{
if (v == p || del[v]) continue;
if (dfs_update(v, u, depth + 1, len)) return 1;
}
hs.pop_back();
return 0;
}
bool dfs_search(int u, int p, int depth, int len)
{
hs.push_back(a[u]);
if (depth * 2 <= len && mp.count(hs.get(depth))) //chi 1 nhanh
return 1;
if (depth == len && hs.isPalin(len))
return 1;
for (auto &v : adj[u])
{
if (v == p || del[v]) continue;
if (dfs_search(v, u, depth + 1, len)) return 1;
}
hs.pop_back();
return 0;
}
bool build(int u, int len)
{
dfs(u, -1);
int centroid = findCentroid(u, -1, sz[u]);
del[centroid] = 1;
for (int turn = 0; turn <= 1; ++turn)
{
mp.clear();
for (auto &v : adj[centroid])
{
if (del[v]) continue;
hs.clear();
if (dfs_search(v, centroid, 1, len))
return 1;
hs.clear();
hs.push_back(a[centroid]);
if (dfs_update(v, centroid, 2, len))
return 1;
}
reverse(all(adj[centroid]));
}
for (auto &v : adj[centroid])
{
if (del[v]) continue;
if (build(v, len)) return 1;
}
return 0;
}
} cd;
bool check(int mid)
{
cd.init();
return cd.build(1, mid);
}
int main()
{
if (ifstream(task".inp")) nx
fast
cin >> n >> a;
a = ' ' + a;
for (int u, v, i = 1; i < n; ++i)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int l = 1, r = (n >> 1), ans = 1;
while(l <= r)
{
int mid = l + r >> 1;
if (check(2 * mid))
{
ans = max(ans, 2 * mid);
l = mid + 1;
}
else r = mid - 1;
}
l = 1, r = (n >> 1);
while(l <= r)
{
int mid = l + r >> 1;
if (check(2 * mid + 1))
{
ans = max(ans, 2 * mid + 1);
l = mid + 1;
}
else r = mid - 1;
}
cout << ans;
}
Compilation message
lampice.cpp: In function 'int main()':
lampice.cpp:190:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
190 | int mid = l + r >> 1;
| ~~^~~
lampice.cpp:202:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
202 | int mid = l + r >> 1;
| ~~^~~
lampice.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:174:31: note: in expansion of macro 'nx'
174 | if (ifstream(task".inp")) nx
| ^~
lampice.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:174:31: note: in expansion of macro 'nx'
174 | if (ifstream(task".inp")) nx
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 4 |
Correct |
17 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5075 ms |
6580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5066 ms |
5288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 4 |
Correct |
17 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Execution timed out |
5075 ms |
6580 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
