Submission #765768

#	Time	Username	Problem	Language	Result	Execution time	Memory
765768		boyliguanhan	Lampice (COCI19_lampice)	C++17	0 / 110	5059 ms	6392 KiB

lampice

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
string S;
vector<int> adj[50100];
int pw[50100];
int I, ans = 0;
void dfs(int x, int len, long long h, long long h2, int p) {
    h = (h*27+S[x-1]-'a'+1)%99999999999999997;
    h2 = (h2+pw[len-1]*(S[x-1]-'a'+1))%99999999999999997;
    if(h==h2) {
        ans = max(ans, len);
    }
    for(auto i: adj[x])
        if(i!=p)
            dfs(i,len+1,h, h2,x);
}
int main() {
    pw[0] = 1;
    for(int i = 1; i <= 50000; i++)
        pw[i] = pw[i-1]*27%99999999999999997;
    int n;
    cin >> n >> S;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(I = 1; I <= n; I++) {
        dfs(I,1,0,0,0);
    }
    cout << ans << '\n';
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37