Submission #202620

#	Time	Username	Problem	Language	Result	Execution time	Memory
202620		rdd6584	Lampice (COCI19_lampice)	C++14	0 / 110	1039 ms	17960 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];

vector<int> v[50002];
int rotn[50002];
char visit[50002];
char s[50002];
int flag, len;

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;
}

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;
}

unordered_map<ll, int> um;
deque<char> dq;

void pcal(int o, int pa, int di, int h1, int h2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1]; // 경로 길이 반환..

    int ha = h1 * rhq[n - di][0] % pr[0];  // 끝의 높이를 n에 맞춰줌
    int hb = h2 * rhq[n - di][1] % pr[1];
    um[ha * pr[1] + hb]++;

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

void mcal(int o, int pa, int di, int h1, int h2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1];

    int ha = h1 * rhq[n - di][0] % pr[0];
    int hb = h2 * rhq[n - di][1] % pr[1];
    um[ha * pr[1] + hb]--;

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

void cal(int o, int pa, int di, int dd, int h1, int h2, int r1, int r2, int s1, int s2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1];
    dq.push_back(s[o]);

    int ha, hb, sa, sb;
    char rev = 0;
    while (dd == 0 || ((di - dd + 1) * 2 + dd > len) && dd <= di) {
        char w = dq.front();
        dq.pop_front();
        rev = w;

        r1 = (r1 + rhq[n - dd][0] * w) % pr[0];
        r2 = (r2 + rhq[n - dd][1] * w) % pr[1];

        s1 = (s1 + rhq[dd][0] * w) % pr[0];
        s2 = (s2 + rhq[dd][1] * w) % pr[1];

        dd++;
    }

    sa = s1 * rhq[n - (dd - 1)][0] % pr[0];
    sb = s2 * rhq[n - (dd - 1)][1] % pr[1];

    ha = (h1 - s1 + pr[0]) % pr[0];
    hb = (h2 - s2 + pr[1]) % pr[1];

    ha = ha * rhq[n - di][0] % pr[0];
    hb = hb * rhq[n - di][1] % pr[1];
    auto t = um.find(ha * pr[1] + hb);

    if (((di - dd + 1) * 2 + dd == len) && r1 == sa && r2 == sb && t != um.end() && t->second > 0)
        flag = 1;

    if (di < len) {
        for (int i : v[o])
            if (i != pa && !visit[i]) {
                if (o == pa) mcal(i, o, 1, 0, 0);
                cal(i, o, di + 1, dd, h1, h2, r1, r2, s1, s2);
                if (o == pa) pcal(i, o, 1, 0, 0);
            }
    }
    if (rev) dq.push_front(rev);
    dq.pop_back();
}

void go(int o) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    visit[t]++;

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

    um[0] = 50001;
    cal(t, t, 0, 0, 0, 0, 0, 0, 0, 0);
    dq.clear();
    um.clear();

    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);
    }

    int l = 0, r = (n - 1) / 2, mid;
    int ans = 0;
    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, l * 2 + 1);

    l = 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, l * 2);
    printf("%d", ans - 2);

}

Compilation message (stderr)

lampice.cpp: In function 'void cal(int, int, int, int, int, int, int, int, int, int)':
lampice.cpp:85:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     while (dd == 0 || ((di - dd + 1) * 2 + dd > len) && dd <= di) {
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:156: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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37