| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084846 |
2024-09-07T06:05:50 Z |
nmts |
Lampice (COCI19_lampice) |
C++17 |
|
5000 ms |
7352 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;
int n;
vector<int> edges[maxn];
int ans = 1;
char a[maxn];
unordered_map<ll , bool> m;
struct Hash{
ll pw[maxn] , hash_val[maxn] , pre_hash[maxn];
int n ;
void prepare()
{
n = 0;
pw[0] = 1;
for (int i = 1 ; i <= 50000 ; ++i)
pw[i] = pw[i - 1] * base;
}
void push(char c)
{
n++;
hash_val[n] = hash_val[n - 1] * base + c;
pre_hash[n] = pre_hash[n - 1] + c * pw[n - 1];
}
void pop()
{
n--;
}
void clear()
{
n = 0;
}
bool IsPalin(int l)
{
return hash_val[l] == pre_hash[l];
}
ll get(int l)
{
return hash_val[n] - hash_val[n - l] * pw[l];
}
} 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)]) 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)] = 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)) maximize(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:217:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
217 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
55 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
72 ms |
2136 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5043 ms |
7000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5016 ms |
7352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
55 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
72 ms |
2136 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1884 KB |
Output is correct |
| 8 |
Execution timed out |
5043 ms |
7000 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
