oj.uz

답안 #314354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314354 2020-10-19T18:30:24 Z leaked Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 10888 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=99999837;
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.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();
}
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");
//    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
*/

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1792 KB Output is correct
2 Correct 16 ms 1792 KB Output is correct
3 Correct 47 ms 1920 KB Output is correct
4 Correct 64 ms 1920 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 2 ms 1664 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2850 ms 8056 KB Output is correct
2 Correct 3397 ms 8972 KB Output is correct
3 Correct 3726 ms 10480 KB Output is correct
4 Correct 4218 ms 10784 KB Output is correct
5 Correct 4347 ms 10888 KB Output is correct
6 Correct 2801 ms 9344 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5052 ms 8232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1792 KB Output is correct
2 Correct 16 ms 1792 KB Output is correct
3 Correct 47 ms 1920 KB Output is correct
4 Correct 64 ms 1920 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 2 ms 1664 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 2850 ms 8056 KB Output is correct
9 Correct 3397 ms 8972 KB Output is correct
10 Correct 3726 ms 10480 KB Output is correct
11 Correct 4218 ms 10784 KB Output is correct
12 Correct 4347 ms 10888 KB Output is correct
13 Correct 2801 ms 9344 KB Output is correct
14 Execution timed out 5052 ms 8232 KB Time limit exceeded
15 Halted 0 ms 0 KB -