Submission #314385

# Submission time Handle Problem Language Result Execution time Memory
314385 2020-10-19T19:04:38 Z leaked Lampice (COCI19_lampice) C++14
42 / 110
3228 ms 28080 KB
#include <bits/stdc++.h>
//#include "race.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)
//#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+5;
const ll inf=LLONG_MAX/2;
const ld eps = 1e-9;
const int ppp=73;
const int M=9999937;
auto rnd=bind(uniform_int_distribution<ll>(1,1e9),mt19937(time(0)));
short int gp[M];
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){
    int x=(a+b);
    if(x<0)
        x+=M;
    if(x>M)
        x-=M;
    return x;
}
void add(int &a,int b){
    a+=b;
    if(a<0)
        a+=M;
    if(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){
    if(ok)
        return;
    a.emplace_back(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(hd,-(s[a[0]]-'a'+1)),pp[N-2]));
    }
    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();
}
vec<int>lol[N];
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;
    vec<vec<int>>lol(sz(g[v]),vec<int>());
    int i=-1;
    for(auto &z : g[v]){
        i++;
        if(used[z]) continue;
        dfs(z,v,len,s[v]-'a'+1,s[v]-'a'+1,2);
        for(auto &q : c){
            gp[q]++;
        }
        lol[i]=c;
        c.clear();
    }
    for(i=0;i<sz(g[v]);++i){
        auto z=g[v][i];
        if(used[z]) continue;
        for(auto &q : lol[i]){
            gp[q]--;
        }
        dfs(z,v,len,s[v]-'a'+1,s[v]-'a'+1,2);
        c.clear();
        lol[i].clear();
    }
    a.clear();
    if(ok)
        return ;
    for(auto &z : g[v]){
        if(!used[z])
            calc(z,len);
    }
}
int n;
signed main(){
    fast_io;
//    ifstream cin("input.txt");
//    gp.reserve(1<<20);
//    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;
}
/*
7
abacaba
1 2
2 3
3 4
4 5
5 6
6 7
7 1
*/
# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 10 ms 5376 KB Output is correct
3 Correct 31 ms 17152 KB Output is correct
4 Correct 36 ms 11632 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2944 KB Output is correct
7 Correct 2 ms 2944 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1583 ms 27000 KB Output is correct
2 Correct 923 ms 27196 KB Output is correct
3 Correct 719 ms 27440 KB Output is correct
4 Correct 772 ms 27704 KB Output is correct
5 Correct 1205 ms 28080 KB Output is correct
6 Correct 197 ms 27756 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 3228 ms 26124 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 10 ms 5376 KB Output is correct
3 Correct 31 ms 17152 KB Output is correct
4 Correct 36 ms 11632 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 2944 KB Output is correct
7 Correct 2 ms 2944 KB Output is correct
8 Correct 1583 ms 27000 KB Output is correct
9 Correct 923 ms 27196 KB Output is correct
10 Correct 719 ms 27440 KB Output is correct
11 Correct 772 ms 27704 KB Output is correct
12 Correct 1205 ms 28080 KB Output is correct
13 Correct 197 ms 27756 KB Output is correct
14 Incorrect 3228 ms 26124 KB Output isn't correct
15 Halted 0 ms 0 KB -