oj.uz

Submission #299575

# Submission time Handle Problem Language Result Execution time Memory
299575 2020-09-15T08:39:03 Z thuanqvbn03 Lampice (COCI19_lampice) C++17
17 / 110
 5000 ms 56568 KB 
//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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48512 KB Output is correct
2 Correct 33 ms 48512 KB Output is correct
3 Correct 32 ms 48632 KB Output is correct
4 Correct 49 ms 48760 KB Output is correct
5 Correct 33 ms 48512 KB Output is correct
6 Correct 29 ms 48504 KB Output is correct
7 Correct 30 ms 48512 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 55032 KB Output is correct
2 Correct 153 ms 55160 KB Output is correct
3 Correct 291 ms 56056 KB Output is correct
4 Correct 300 ms 56568 KB Output is correct
5 Correct 118 ms 56568 KB Output is correct
6 Execution timed out 5036 ms 55160 KB Time limit exceeded

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 54812 KB Output is correct
2 Correct 166 ms 54776 KB Output is correct
3 Correct 261 ms 54008 KB Output is correct
4 Execution timed out 5033 ms 53752 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48512 KB Output is correct
2 Correct 33 ms 48512 KB Output is correct
3 Correct 32 ms 48632 KB Output is correct
4 Correct 49 ms 48760 KB Output is correct
5 Correct 33 ms 48512 KB Output is correct
6 Correct 29 ms 48504 KB Output is correct
7 Correct 30 ms 48512 KB Output is correct
8 Correct 117 ms 55032 KB Output is correct
9 Correct 153 ms 55160 KB Output is correct
10 Correct 291 ms 56056 KB Output is correct
11 Correct 300 ms 56568 KB Output is correct
12 Correct 118 ms 56568 KB Output is correct
13 Execution timed out 5036 ms 55160 KB Time limit exceeded