oj.uz

Submission #199634

# Submission time Handle Problem Language Result Execution time Memory
199634 2020-02-02T12:01:07 Z SamAnd Lampice (COCI19_lampice) C++17
25 / 110
 5000 ms 13132 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 50004;
const long long P = 37;
const int M = 1700700007;
long long ast[N];

int n;
char u[N];
vector<int> a[N];

bool c[N];

int q[N];
void dfs0(int x, int p)
{
    q[x] = 1;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h] || h == p)
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }
}

int dfsc(int x, int p, int xx)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h] || h == p)
            continue;
        if (q[h] > q[xx] / 2)
            return dfsc(h, x, xx);
    }
    return x;
}

int d[N];
int up[N], down[N];

multiset<int> s[N];

void dfs1(int x, int p)
{
    if (x == p)
    {
        d[x] = 0;
        up[x] = down[x] = u[x];
    }
    else
    {
        d[x] = d[p] + 1;
        up[x] = (u[x] + P * up[p]) % M;
        down[x] = (down[p] + ast[d[x]] * u[x]) % M;
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h] || h == p)
            continue;
        dfs1(h, x);
    }
    s[d[x]].clear();
}

void dfs11(int x, int p, int xx)
{
    s[d[x]].insert((up[x] - (up[xx] * ast[d[x]]) % M + M) % M);
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h])
            continue;
        dfs11(h, x, xx);
    }
}

void dfs12(int x, int p, int xx)
{
    s[d[x]].erase(s[d[x]].find((up[x] - (up[xx] * ast[d[x]]) % M + M) % M));
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h])
            continue;
        dfs12(h, x, xx);
    }
}

vector<int> v;
bool dfs13(int x, int p, int m)
{
    v.push_back(x);
    int xx = m - (d[x] + 1);
    int yy = (d[x] + 1) - xx;
    if (xx >= 0 && yy >= 1)
    {
        if (up[v[yy - 1]] == down[v[yy - 1]])
        {
            if (s[xx].find((up[x] - (up[v[yy - 1]] * ast[d[x] - d[v[yy - 1]]]) % M + M) % M) != s[xx].end())
            {
                return true;
            }
        }
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p || c[h])
            continue;
        if (dfs13(h, x, m))
            return true;
    }
    v.pop_back();
    return false;
}

bool stgg(int x, int m)
{
    dfs1(x, x);
    dfs11(x, x, x);
    v.clear();
    v.push_back(x);
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (c[h])
            continue;
        dfs12(h, x, x);
        if (dfs13(h, x, m))
            return true;
        dfs11(h, x, x);
    }
    return false;
}

bool stg(int m)
{
    memset(c, false, sizeof c);
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        dfs0(x, x);
        x = dfsc(x, x, x);
        if (stgg(x, m))
            return true;
        c[x] = true;
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i];
            if (!c[h])
                q.push(h);
        }
    }
    return false;
}

int byn1()
{
    int l = 1;
    int r = n;
    if (r % 2 == 0)
        --r;
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (m % 2 == 0)
            ++m;
        if (stg(m))
        {
            ans = m;
            l = m + 2;
        }
        else
            r = m - 2;
    }
    return ans;
}

int byn0()
{
    int l = 2;
    int r = n;
    if (r % 2 == 1)
        --r;
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (m % 2 == 1)
            ++m;
        if (stg(m))
        {
            ans = m;
            l = m + 2;
        }
        else
            r = m - 2;
    }
    return ans;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    ast[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        ast[i] = (ast[i - 1] * P) % M;
    }
    scanf("%d", &n);
    scanf(" %s", (u + 1));
    for (int i = 1; i <= n; ++i)
    {
        u[i] = (u[i] - 'a' + 1);
    }
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    printf("%d\n", max(byn1(), byn0()));
    return 0;
}

Compilation message

lampice.cpp: In function 'void dfs0(int, int)':
lampice.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'int dfsc(int, int, int)':
lampice.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs1(int, int)':
lampice.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs11(int, int, int)':
lampice.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'void dfs12(int, int, int)':
lampice.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool dfs13(int, int, int)':
lampice.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stgg(int, int)':
lampice.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
lampice.cpp: In function 'bool stg(int)':
lampice.cpp:154:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:218:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:219:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", (u + 1));
     ~~~~~^~~~~~~~~~~~~~~~
lampice.cpp:227:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4344 KB Output is correct
2 Correct 31 ms 4344 KB Output is correct
3 Correct 78 ms 4472 KB Output is correct
4 Correct 99 ms 4472 KB Output is correct
5 Incorrect 8 ms 4396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3815 ms 11384 KB Output is correct
2 Correct 2605 ms 12024 KB Output is correct
3 Correct 1757 ms 12412 KB Output is correct
4 Correct 1727 ms 12664 KB Output is correct
5 Correct 2855 ms 13132 KB Output is correct
6 Correct 233 ms 12924 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4344 KB Output is correct
2 Correct 31 ms 4344 KB Output is correct
3 Correct 78 ms 4472 KB Output is correct
4 Correct 99 ms 4472 KB Output is correct
5 Incorrect 8 ms 4396 KB Output isn't correct
6 Halted 0 ms 0 KB -