oj.uz

Submission #777576

# Submission time Handle Problem Language Result Execution time Memory
777576 2023-07-09T10:55:29 Z ElyesChaabouni Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 4688 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define vi vector<int>
#define pb push_back
#define forr(i , x , y) for(int i = x; i<=y;i++)
#define fore(i , n) for(int i = 0;i<n;i++)
#define se second
#define nl '\n'
#define fi first
#define sz(s) s.size()
const int N = 50001;
vi adj[N];
int n ;
string s;
//int depth[N];
int par[N];
void dfs(int x , int p)
{
    for(auto u : adj[x])
    {
        if(u == p)continue;
        par[u] = x;
        dfs(u , x);
    }
}
bool check(string &t)
{
    int x = sz(t);
    fore(i , x/2)
    {
        if(t[i]!=t[x - i - 1])return 0;
    }
    return 1;
}
string getPath(int j)
{
    string ret = "";
    while(j != -1)
    {
        ret+=(char)s[j];
        j = par[j];
    }
//    cout<<ret<<nl;
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--)
    {
        cin>>n;
        cin>>s;
        fore(i , n)
        {
            adj[i].clear();
        }
        fore(i , n - 1)
        {
            int u , v;
            cin>>u>>v;
            u--;v--;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        int cnt = 0;
        int mxL = 0;
        fore(i , n)
        {
            if(cnt >= 500000)
                    break;
            fore(j , n)
            {
                par[j] = -1;
            }
            dfs(i , -1);

            forr(j , i , n - 1)
            {
                string v = getPath(j);
                cnt++;
                if(check(v))
                {
//                    cout<<v<<nl;
                    mxL = max(mxL , (int)sz(v));
                }
            }
        }
        cout<<mxL<<nl;
    }
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1492 KB Output is correct
2 Correct 19 ms 1540 KB Output is correct
3 Correct 104 ms 1548 KB Output is correct
4 Incorrect 143 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5035 ms 4688 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 5065 ms 4240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1492 KB Output is correct
2 Correct 19 ms 1540 KB Output is correct
3 Correct 104 ms 1548 KB Output is correct
4 Incorrect 143 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -