Submission #777576

#	Time	Username	Problem	Language	Result	Execution time	Memory
777576		ElyesChaabouni	Lampice (COCI19_lampice)	C++14	0 / 110	5065 ms	4688 KiB

lampice

#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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37