| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084842 |
2024-09-07T05:52:17 Z |
nmts |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
8552 KB |
#include <bits/stdc++.h>
#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define endl '\n'
#define ll long long
const int maxn = 5e4 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
template <class T> inline T sqr(T x) { return x * x; };
template <class T> inline int Power(T x, int y)
{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
inline int gcd(int x, int y)
{ return y ? gcd(y , x % y) : x;}
inline int lcm(int x, int y) { return x * y / gcd(x, y); }
using namespace std;
const int base = 311;
const int nmod = 2;
const ll modHash[4] = {(int)1e9 + 2277, (int)1e9 + 5277 , (int)1e9 + 8277 , (int)1e9 + 9277};
int n;
vector<int> edges[maxn];
int ans = 1;
char a[maxn];
map<pii , bool> m;
struct Hash{
int pw[maxn][nmod] , hash_val[maxn][nmod] , pre_hash[maxn][nmod];
int n ;
void prepare()
{
n = 0;
for (int i = 0 ; i < nmod ; ++i)
pw[0][i] = 1;
for (int i = 1 ; i <= 50000 ; ++i)
for (int j = 0 ; j < nmod ; ++j)
pw[i][j] = pw[i - 1][j] * base % modHash[j];
}
void push(char c)
{
n++;
for (int i = 0 ; i < nmod ; ++i)
hash_val[n][i] = (hash_val[n - 1][i] * base + c) % modHash[i],
pre_hash[n][i] = (pre_hash[n - 1][i] + c * pw[n - 1][i]) % modHash[i];
}
void pop()
{
n--;
}
void clear()
{
n = 0;
}
bool IsPalin(int l)
{
return hash_val[l][1] == pre_hash[l][1] && hash_val[l][0] == pre_hash[l][0];
}
ll get(int l , int pos)
{
return hash_val[n][pos] - hash_val[n - l][pos] * pw[l][pos];
}
} hs;
struct CD{
int sz[maxn];
bool del[maxn];
void init()
{
for (int i = 1 ; i <= n ; ++i) del[i] = 0;
}
void dfs(int u , int p)
{
sz[u] = 1;
for (int v : edges[u])
if (v != p && del[v] == 0)
{
dfs(v , u);
sz[u] += sz[v];
}
}
int find_centroid(int u , int p)
{
for (int v : edges[u])
if (v != p)
if (sz[v] > n / 2 && del[v] == 0)
return find_centroid(v , u);
return u;
}
bool get(int u , int p , int hight , int len)
{
hs.push(a[u]);
if (2 * hight <= len && m[{hs.get(hight , 0) , hs.get(hight , 1)}]) return 1;
if (hight == len && hs.IsPalin(len)) return 1;
for (int v : edges[u])
if (v != p && del[v] == 0)
{
if (get(v , u , hight + 1 , len)) return 1;
}
hs.pop();
return 0;
}
bool update(int u , int p , int hight , int len)
{
hs.push(a[u]);
if (hight * 2 >= len && hs.IsPalin(hight * 2 - len))
m[{hs.get(len - hight , 0) , hs.get(len - hight , 1)}] = 1;
if (hight == len && hs.IsPalin(len)) return 1;
for (int v : edges[u])
if (v != p && del[v] == 0)
{
if (update(v , u , hight + 1 , len)) return 1;
}
hs.pop();
return 0;
}
bool decompose(int u , int len)
{
dfs(u , 0);
int c = find_centroid(u , 0);
del[c] = 1;
for (int turn = 1 ; turn <= 2 ; ++turn)
{
m.clear();
for (int v : edges[c])
if (del[v] == 0)
{
hs.clear();
if (get(v , c , 1 , len)) return 1;
hs.clear();
hs.push(a[c]);
if (update(v , c , 2 , len)) return 1;
}
reverse(edges[c].begin() , edges[c].end());
}
for (int v : edges[u])
if (del[v] == 0)
{
if (decompose(v , len)) return 1;
}
return 0;
}
} cd;
void tknp(int l , int r, int ok)
{
while (l <= r )
{
int mid = l + r >> 1;
cd.init();
if (cd.decompose(1 , 2 * mid + ok)) ans = 2 * mid + ok , l = mid + 1;
else r = mid - 1;
}
}
void solve()
{
hs.prepare();
cin >> n ;
for (int i = 1 ; i <= n ; ++i) cin >> a[i];
for (int i = 1 ; i < n ; ++i)
{
int u , v ; cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
tknp(1 , n >> 1 , 0);
tknp(1 , n >> 1 , 1);
cout << ans << endl;
}
int32_t main()
{
faster;
// file("txt");
// int t ; cin >> t ; while (t--)
solve();
return 0;
}
Compilation message
lampice.cpp: In function 'void tknp(int, int, int)':
lampice.cpp:222:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
222 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5033 ms |
8264 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5023 ms |
8552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
