| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 516362 |
2022-01-21T08:22:59 Z |
leaked |
Lampice (COCI19_lampice) |
C++14 |
|
5000 ms |
35408 KB |
#include <bits/stdc++.h>
//#include "debug.h"
// #pragma GCC optimize("-O3")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define f first
#define s second
#define se second
#define vec vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1ll<<x)
#define p_b push_back
#define m_p make_pair
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define sq(x) (x)*(x)
using namespace std;
using namespace __gnu_pbds;
typedef pair<long long, long long> PII;
typedef pair<int, int> pii;
typedef long double ld;
typedef long long ll;
typedef pair<long long, long long > pll;
//template <typename T> umax(T &a, T b){return (a<b ? a=b,1 : 0);}
//template <typename T> umin(T &a, T b){return (a>b ? a=b,1 : 0);}
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> o_set;
const int N=5e4+5;
const ll inf=1e9;
const ld eps = 1e-9;
const int ppp=73;
const int M=99999837;
const ll tx[4]={-1,1,0,0};
const ll ty[4]={0,0,-1,1};
const char rev_to[4]={'U','D','L','R'};
auto rnd=bind(uniform_int_distribution<ll>(1,1e9),mt19937(time(0)));
int dp[N],TO[N];
bool used[N];
vec<int>g[N];
int pp[N];
void recalc(int v,int p){
dp[v]=1;
for(auto &z : g[v]){
if(!used[z] && z!=p){
recalc(z,v);
dp[v]+=dp[z];
}
}
}
int get_cen(int v,int p,int sz){
for(auto &z : g[v]){
if(z^p && !used[z] && dp[z]>=sz/2){
return get_cen(z,v,sz);
}
}
return v;
}
int sum(int x,int b){
x+=b;
if(x>=M)
x-=M;
if(x<0)
x+=M;
return x;
}
void add(int &x,int b){
x+=b;
if(x<0)
x+=M;
if(x>=M)
x-=M;
}
int mult(const int &a,const int &b){
return 1ll*a*b%M;
}
int ok;
map<int,int> gp[N];
int len,n,m;
vec<int>hd;
string s;
int Hd[N],Hup[N];
void calc_hd(int v,int p,int to,int dst){
if(dst>(len/2))
return;
Hd[v]=sum(mult(s[v]-'a'+1,pp[dst-1]),Hd[p]);
gp[dst][mult(Hd[v],pp[N-1])]+=to;
// debug()<<imie(v)imie(mult(Hd[v],pp[N-dst-1]));
// if(dst<=(len/2)){
for(auto &z : g[v]){
if(!used[z] && z^p){
calc_hd(z,v,to,dst+1);
}
}
// }
}
vec<int>a;
void calc_hupd(int v,int p,int dl){
a.pb(v);
Hup[v]=sum(mult(ppp,Hup[p]),s[v]-'a'+1);
Hd[v]=sum(mult(s[v]-'a'+1,pp[dl-1]),Hd[p]);
// debug()<<imie(v)imie(Hd[v])imie(Hup[v]);
if(dl>=(len+1)/2 && dl<len){
int rem=len-dl;
int mh=Hd[v];
if(dl-rem){
int pr=a[dl-rem-1];
add(mh,-Hd[pr]);
if(Hd[pr]==Hup[pr]){
mh=mult(mh,pp[N-(dl-rem)-1]);
// debug()<<imie(rem)imie(gp[rem])imie(mh);
ok|=gp[rem][mh];
}
}
else{
mh=mult(mh,pp[N-1]);
ok|=gp[rem][mh];
}
}
else if(dl>=len){
if(dl!=len){
add(Hup[v],-mult(pp[len],s[a[dl-len-1]]-'a'+1));
int u=a[dl-len-1];
add(Hd[v],-mult(pp[TO[u]-1],s[u]-'a'+1));
}
ok|=(mult(Hup[v],pp[N-1])==mult(Hd[v],pp[N-(dl-len)-1]));
}
for(auto &z : g[v]){
if(!used[z] && z^p){
TO[v]=z;
calc_hupd(z,v,dl+1);
}
}
a.pop_back();
}
void dfs(int v){
recalc(v,v);
v=get_cen(v,v,dp[v]);
used[v]=1;
Hd[v]=s[v]-'a'+1;
Hup[v]=s[v]-'a'+1;
a.pb(v);
for(int i = 1; i >=-1; --i){
if(!i)
continue;
for(auto &z : g[v]){
if(!used[z]){
TO[v]=z;
if(i==1){
Hd[v]=s[v]-'a'+1;
calc_hupd(z,v,2);
Hd[v]=0;
calc_hd(z,v,i,1);
}
else{
Hd[v]=0;
calc_hd(z,v,i,1);
Hd[v]=s[v]-'a'+1;
calc_hupd(z,v,2);
}
// cout<<endl;
}
}
// reverse(all(g[v]));
}
a.pop_back();
if(ok)
return ;
for(auto &z : g[v]){
if(!used[z])
dfs(z);
}
}
signed main()
{
fast_io;
pp[0]=1;
for(int i = 1 ; i < N; ++i)
pp[i]=mult(pp[i-1],ppp);
cin>>n;
cin>>s;
for(int i = 1 ; i < n; i++){
int v,u;
cin>>v>>u;--v;--u;
g[v].pb(u);
g[u].pb(v);
}
int ans=1;
for(int i = 0 ; i <= 1 ;i ++){
int l=1,r=n/2+1;
while(l!=r){
int mid=(l+r)>>1;
len=2*mid+i;
ok=0;
fill(used,used+n,false);
dfs(0);
if(ok){
l=mid+1;
}
else{
r=mid;
}
}
l--;
ans=max(ans,2*l+i);
}
cout<<ans;
return 0;
}
/*
4
abba
1 2
2 3
3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4056 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4052 KB |
Output is correct |
| 3 |
Correct |
38 ms |
4436 KB |
Output is correct |
| 4 |
Correct |
45 ms |
4320 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4044 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4044 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3228 ms |
30532 KB |
Output is correct |
| 2 |
Correct |
2770 ms |
28660 KB |
Output is correct |
| 3 |
Correct |
1674 ms |
24536 KB |
Output is correct |
| 4 |
Correct |
1772 ms |
26020 KB |
Output is correct |
| 5 |
Correct |
4611 ms |
35408 KB |
Output is correct |
| 6 |
Correct |
201 ms |
11480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5100 ms |
29656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4056 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4052 KB |
Output is correct |
| 3 |
Correct |
38 ms |
4436 KB |
Output is correct |
| 4 |
Correct |
45 ms |
4320 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4044 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4044 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4044 KB |
Output is correct |
| 8 |
Correct |
3228 ms |
30532 KB |
Output is correct |
| 9 |
Correct |
2770 ms |
28660 KB |
Output is correct |
| 10 |
Correct |
1674 ms |
24536 KB |
Output is correct |
| 11 |
Correct |
1772 ms |
26020 KB |
Output is correct |
| 12 |
Correct |
4611 ms |
35408 KB |
Output is correct |
| 13 |
Correct |
201 ms |
11480 KB |
Output is correct |
| 14 |
Execution timed out |
5100 ms |
29656 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
