Submission #202843

#	Time	Username	Problem	Language	Result	Execution time	Memory
202843		rdd6584	Lampice (COCI19_lampice)	C++14	110 / 110	3587 ms	58796 KiB

lampice

#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 };
ll rhq[50001][2];
int dh[17][50001][2];
int rh[17][50001][2];
int pal[17][50001];
int ro[17][50001];
vector<int> v[50001];

unordered_map<ll, int> um[50001];
int rotn[50001];
char visit[50001];
char s[50001];
int ha, hb;

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

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

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

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

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

int pre(int o, int pa) {
    int ret = 1;
    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, int root) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1];
    ha = h1 * rhq[n - di][0] % pr[0];
    hb = h2 * rhq[n - di][1] % pr[1];
    um[root][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, root);
    }
}

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

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

        if (um[root].find(ha * pr[1] + hb) != um[root].end() && um[root][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, dep, root);

    road.pop_back();
}

void gopre(int o, int dep) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    ro[dep][o] = t;
    visit[t]++;
    um[t][0] = 100000;
    preHash(t, t, 0, dep);

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

    for (int &i : v[t])
        if (!visit[i] && !flag)
            gopre(i, dep + 1);

    visit[t]--;
}


void go(int o, int dep) {
    int t = ro[dep][o];
    visit[t]++;

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

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

    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] = rhq[i - 1][0] * B % pr[0];
        rhq[i][1] = rhq[i - 1][1] * B % pr[1];
    }

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

    len = n;
    gopre(0, 0);

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

Compilation message (stderr)

lampice.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
lampice.cpp: In function 'int main()':
lampice.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:148: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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37