oj.uz

Submission #202760

# Submission time Handle Problem Language Result Execution time Memory
202760 2020-02-17T21:45:35 Z rdd6584 Lampice (COCI19_lampice) C++14
17 / 110
 5000 ms 9720 KB 
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef long long ll;

int n;
const int B = 100007;
const ll pr[2] = { 1000000009, 1000000021 };
int rhq[50002][2], dh[50002][2], rh[50002][2];
char pal[50002];
vector<int> v[50002];

map<ll, int> um;
int rotn[50002];
char visit[50002];
char s[50002];
int ha, hb;

vector<int> road;
int len, flag, ans = 1;

int pre(int o, int pa) {
    int ret = 1;
    pal[o] = 0;
    for (int &i : v[o])
        if (i != pa && !visit[i])
            ret += pre(i, o);
    return rotn[o] = ret;
}

int cent(int o, int pa, int cap) {
    for (int &i : v[o])
        if (i != pa && !visit[i] && rotn[i] > cap)
            return cent(i, o, cap);
    return o;
}

void pl(int o, int pa, int di, int h1, int h2, int fl) {
    h1 = (h1 + (ll)rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + (ll)rhq[di][1] * s[o]) % pr[1];
    ha = h1 * (ll)rhq[n - di][0] % pr[0];
    hb = h2 * (ll)rhq[n - di][1] % pr[1];
    um[ha * pr[1] + hb] += fl;

    if (di < len)
        for (int &i : v[o])
            if (i != pa && !visit[i])
                pl(i, o, di + 1, h1, h2, fl);
}

void preHash(int o, int pa, int di) {
    dh[o][0] = (dh[pa][0] + (ll)rhq[di][0] * s[o]) % pr[0];
    dh[o][1] = (dh[pa][1] + (ll)rhq[di][1] * s[o]) % pr[1];

    rh[o][0] = (rh[pa][0] + (ll)rhq[n - di][0] * s[o]) % pr[0];
    rh[o][1] = (rh[pa][1] + (ll)rhq[n - di][1] * s[o]) % pr[1];

    if (rh[o][0] == dh[o][0] * (ll)rhq[n - di][0] % pr[0] &&
        rh[o][1] == dh[o][1] * (ll)rhq[n - di][1] % pr[1])
        pal[o] = 1;

    if (di < len) {
        for (int &i : v[o])
            if (i != pa && !visit[i])
                preHash(i, o, di + 1);
    }
}

void cal(int o, int pa, int di) {
    road.push_back(o);
    int p = 2 * di + 1 - len;

    if (sz(road) > p && p >= 0 && pal[road[p]]) {
        ha = (dh[o][0] - dh[road[p]][0] + pr[0]) * rhq[n - di][0] % pr[0];
        hb = (dh[o][1] - dh[road[p]][1] + pr[1]) * rhq[n - di][1] % pr[1];

        if (um.find(ha * pr[1] + hb) != um.end() && um[ha * pr[1] + hb] >= 1)
            flag = 1;
    }

    if (di < len && !flag)
        for (int &i : v[o])
            if (i != pa && !visit[i])
                cal(i, o, di + 1);

    road.pop_back();
}

void go(int o) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    visit[t]++;
    um.clear();
    um[0] = 100000;
    preHash(t, 50001, 0);

    for (int &i : v[t])
        if (!visit[i])
            pl(i, t, 1, 0, 0, 1);

    road.push_back(t);
    for (int &i : v[t])
        if (!visit[i] && !flag) {
            pl(i, t, 1, 0, 0, -1);
            cal(i, t, 1);
            pl(i, t, 1, 0, 0, 1);
        }
    road.pop_back();

    for (int &i : v[t])
        if (!visit[i] && !flag)
            go(i);

    visit[t]--;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s);

    rhq[0][0] = rhq[0][1] = 1;
    for (int i = 1; i <= n; i++) {
        rhq[i][0] = (ll)rhq[i - 1][0] * B % pr[0];
        rhq[i][1] = (ll)rhq[i - 1][1] * B % pr[1];
    }

    int a, b;
    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d", &a, &b);
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int l = 1, r = (n - 1) / 2, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        flag = 0;
        len = mid * 2 + 1;
        go(0);
        if (flag) l = mid + 1;
        else r = mid - 1;
    }
    ans = max(ans, r * 2 + 1);

    l = ans / 2 + 1, r = n / 2;
    while (l <= r) {
        mid = (l + r) / 2;
        flag = 0;
        len = mid * 2;
        go(0);
        if (flag) l = mid + 1;
        else r = mid - 1;
    }
    ans = max(ans, r * 2);
    printf("%d", ans);
}

Compilation message

lampice.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
lampice.cpp: In function 'int main()':
lampice.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1532 KB Output is correct
2 Correct 22 ms 1660 KB Output is correct
3 Correct 84 ms 1656 KB Output is correct
4 Correct 101 ms 1784 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4446 ms 9592 KB Output is correct
2 Execution timed out 5046 ms 9720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1532 KB Output is correct
2 Correct 22 ms 1660 KB Output is correct
3 Correct 84 ms 1656 KB Output is correct
4 Correct 101 ms 1784 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct
8 Correct 4446 ms 9592 KB Output is correct
9 Execution timed out 5046 ms 9720 KB Time limit exceeded
10 Halted 0 ms 0 KB -