Submission #202700

#	Time	Username	Problem	Language	Result	Execution time	Memory
202700		rdd6584	Lampice (COCI19_lampice)	C++14	17 / 110	1385 ms	9640 KiB

lampice

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const long double PI = 3.141592653589793238462643383279502884197;

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

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

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 + 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[ha * pr[1] + hb] += fl;

    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] + rhq[di][0] * s[o]) % pr[0];
    dh[o][1] = (dh[pa][1] + rhq[di][1] * s[o]) % pr[1];

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

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

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

vector<int> road; // 여태까지 온 길을 기억한다.
int len, flag, ans = 1; // len이 0이면?
// 같은거였을 경우.
void cal(int o, int pa, int di) {
    road.push_back(o);
    int p = 2 * di + 1 - len; // p~di까지가 범위. road[p - 1]는

    // printf("%d : %d %d %d//\n", o, len, p + 1, di);
    if (sz(road) > p && p >= 0 && pal[road[p]]) {
        // printf("pass!! %d %d\n", dh[o][0] - dh[road[p]][0], dh[o][1] - dh[road[p]][1]);

        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) {
            // printf("pass %d : %d %d %d//\n", o, len, p + 1, di);
            flag = 1;
        }
    }

    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]) {
            pl(i, t, 1, 0, 0, -1);

            int l = 1, r = (rotn[o] - 1) / 2, mid;
            while (l <= r) {
                mid = (l + r) / 2;
                flag = 0;
                len = mid * 2 + 1;

                cal(i, t, 1);
                // f("%d %d : %d %d\n", t, i, len, flag);

                if (flag) l = mid + 1;
                else r = mid - 1;
            }
            ans = max(ans, r * 2 + 1);

            l = 1, r = rotn[o] / 2;
            while (l <= r) {
                mid = (l + r) / 2;
                flag = 0;
                len = mid * 2;

                cal(i, t, 1);
                // printf("%d %d : %d %d\n", t, i, len, flag);

                if (flag) l = mid + 1;
                else r = mid - 1;
            }
            ans = max(ans, r * 2);

            pl(i, t, 1, 0, 0, 1);
        }
    road.pop_back();

    for (int i : v[t])
        if (!visit[i])
            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++)
        for (int j = 0; j < 2; j++)
            rhq[i][j] = rhq[i - 1][j] * B % pr[j];

    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);
    }
    go(0);

    printf("%d", ans);
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:161:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:171: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: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37