| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 314338 |
2020-10-19T18:10:28 Z |
leaked |
Lampice (COCI19_lampice) |
C++14 |
|
5000 ms |
8496 KB |
#include <bits/stdc++.h>
//#include "race.h"
#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)
//#define int long long
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+1;
const ll inf=LLONG_MAX/2;
const ld eps = 1e-9;
const int ppp=73;
const int M=99999937;
auto rnd=bind(uniform_int_distribution<ll>(1,1e9),mt19937(time(0)));
gp_hash_table<int,bool>gp;
vec<int> g[N];
bool used[N];
int dp[N];
int mult(int a,int b){
return 1ll*a*b%M;
}
int plues(int a,int b){
return (a+b+M)%M;
}
void add(int &a,int b){
a+=b;
a+=M;
a%=M;
}
void recaclc(int v,int p){
dp[v]=1;
for(auto &z : g[v]){
if(z^p && !used[z])
recaclc(z,v),dp[v]+=dp[z];
}
}
int get_cen(int v,int p,int sz){
for(auto &z : g[v]){
if(!used[z] && z^p && dp[z]>=(sz+1)/2)
return get_cen(z,v,sz);
}
return v;
}
vec<int>a;
vec<int>c;
string s;
int pp[N];
int Hd[N];
int Hup[N];
int TO[N];
bool ok;
int done;
void dfs(int v,int p,int len,int hd,int hup,int dl){
a.pb(v);
hd=plues(mult(s[v]-'a'+1,pp[dl-1]),hd);
hup=plues(mult(hup,ppp),s[v]-'a'+1);
Hd[v]=hd;
Hup[v]=hup;
TO[v]=dl;
if((dl-1)<=len/2){
c.pb(mult(plues(hup,-mult(pp[dl-1],s[a[0]]-'a'+1)),pp[N-1]));
}
if(dl>=(len+1)/2 && dl<len){
int rem=len-dl;
int mh=hd;
// debug()<<imie(gp);
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]);
ok|=gp[mh];
}
}
else{
mh=mult(mh,pp[N-1]);
ok|=gp[mh];
}
}
else if(dl>=len){
if(dl!=len){
add(hup,-mult(pp[len],s[a[dl-len-1]]-'a'+1));
int u=a[dl-len-1];
add(hd,-mult(pp[TO[u]-1],s[u]-'a'+1));
}
ok|=(mult(hup,pp[N-1])==mult(hd,pp[N-(dl-len)-1]));
}
for(auto &z : g[v]){
if(!used[z] && z!=p){
dfs(z,v,len,hd,hup,dl+1);
}
}
a.pop_back();
}
void calc(int v,int len){
recaclc(v,v);
v=get_cen(v,v,dp[v]);
used[v]=1;
a.pb(v);
Hd[v]=s[v]-'a'+1;
Hup[v]=s[v]-'a'+1;
for(int i = 0; i < 2;i++){
gp.clear();
for(auto &z : g[v]){
if(used[z]) continue;
dfs(z,v,len,s[v]-'a'+1,s[v]-'a'+1,2);
for(auto &z : c){
gp[z]=1;
}
c.clear();
}
reverse(all(g[v]));
}
a.clear();
for(auto &z : g[v]){
if(!used[z])
calc(z,len);
}
}
int n;
signed main(){
fast_io;
// ifstream cin("input.txt");
// cout << fixed << LLONG_MAX/3 << "\n" << 1e18;
cin>>n;
cin>>s;
pp[0]=1;
for(int i = 1 ;i < N; ++i)
pp[i]=mult(ppp,pp[i-1]);
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<2;i++){
int l=1,r=n/2+1;
while(l!=r){
fill(used,used+n,false);
ok=0;
int tm=(l+r)>>1;
calc(0,2*tm+i);
if(ok)
l=tm+1;
else
r=tm;
}
l--;
// umax(ans,2*l+i);
ans=max(ans,2*l+i);
}
cout<<ans;
return 0;
}
/*
4
amma
1 2
2 3
3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2877 ms |
7964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5055 ms |
8496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
