oj.uz

Submission #765768

# Submission time Handle Problem Language Result Execution time Memory
765768 2023-06-25T04:56:57 Z boyliguanhan Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 6392 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5038 ms 6392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5059 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -