Submission #299575

#	Time	Username	Problem	Language	Result	Execution time	Memory
299575		thuanqvbn03	Lampice (COCI19_lampice)	C++17	17 / 110	5036 ms	56568 KiB

lampice

//thuanqvbn03
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 50005;

struct LCA
{
    int Time = 0;
    int start[MaxN];
    pair<int, int> RMQ[2 * MaxN][21];
    void Start(int u, int Depth)
    {
        Time++;
        start[u] = Time;
        RMQ[Time][0] = make_pair(Depth, u);
    }
    void Add(int u, int Depth)
    {
        Time++;
        RMQ[Time][0] = make_pair(Depth, u);
    }
    void Build()
    {
        int Log = log2(Time);
        for (int t = 1; t <= Log; t++)
        {
            int j = (1 << (t - 1));
            for (int i = Time - 2 * j + 1; i > 0; i--)
            {
                RMQ[i][t] = min(RMQ[i][t - 1], RMQ[i + j][t - 1]);
            }
        }
    }
    int Get(int u, int v)
    {
        u = start[u];
        v = start[v];
        if (u > v)
        {
            swap(u, v);
        }
        int Log = log2(v - u + 1);
        return min(RMQ[u][Log], RMQ[v - (1 << Log) + 1][Log]).second;
    }
};

int n;
string s;
vector<int> Adj[MaxN], aAdj[MaxN][26];
int depth[MaxN], Pd[MaxN];
int Ans;
LCA lca;

void DFS(int u)
{
    lca.Start(u, depth[u]);
    for (auto v : Adj[u])
    {
        if (v != Pd[u])
        {
            Pd[v] = u;
            depth[v] = depth[u] + 1;
            DFS(v);
            lca.Add(u, depth[u]);
        }
    }
}

int dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[lca.Get(u, v)];
}

void Solve(int u, int v)
{
    int d = dist(u, v);
    Ans = max(Ans, d);
    for (int i = 0; i < 26; i++)
    {
        for (auto x : aAdj[u][i])
        {
            for (auto y : aAdj[v][i])
            {
                if (dist(x, y) == d + 2)
                {
                    Solve(x, y);
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s;
    s = " " + s;
    int u, v;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
        aAdj[u][s[v] - 'a'].push_back(v);
        aAdj[v][s[u] - 'a'].push_back(u);
    }
    depth[1] = 0;
    DFS(1);
    lca.Build();
    Ans = 0;
    for (int i = 1; i <= n; i++)
    {
        Solve(i, i);
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto j : Adj[i])
        {
            if (s[i] == s[j] && j != Pd[i])
            {
                Solve(i, j);
            }
        }
    }
    cout << Ans + 1;
    return 0;
}

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