Submission #202590

#	Time	Username	Problem	Language	Result	Execution time	Memory
202590		rdd6584	Lampice (COCI19_lampice)	C++14	25 / 110	974 ms	11432 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[50001];
int rotn[50001];
char visit[50001];
char s[50001];
int flag = 0, 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, pii> um; // 개수만으로 바꿔줘도 됨.

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

    auto t = um.find(ha + hb * pr[1]);


    if (t == um.end()) um[ha + hb * pr[1]] = {1, di};
    else t->second.first++;

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

// 당겨야 함.. 길이가 얼만큼인지 아니까..
// 계산할 때, 위치 정규화 시켜줘야 함.
// dd는 문자열 시작점의 높이
// 큐에서 가장 최근 문자를 뺀다
deque<char> dq;
int root;

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

    // h1 - s1이 해당 경로를 의미.
    int ha = (h1 - s[root] + pr[0]) % pr[0] * rhq[n - di][0] % pr[0];
    int hb = (h2 - s[root] + pr[1]) % pr[1] * rhq[n - di][1] % pr[1];
    ll th = ha + hb * pr[1];
    dq.push_back(s[o]);
    um[th].first--;

    // dd까지 들어가 있다.. 그러니까 이제 뺏을 차례인 곳임.
    // can이면 dd만큼 더함.
    // 항상 같다는 전제니까 dd-di+1
    vector<char> rev;
    while (dd <= di) {
        ha = (h1 - s1 + pr[0]) % pr[0];
        hb = (h2 - s2 + pr[1]) % pr[1];

        // printf("befo %d %d ha hb//\n", ha, hb);

        ha = ha * rhq[n - di][0] % pr[0];
        hb = hb * rhq[n - di][1] % pr[1];
        auto t = um.find(ha + hb * pr[1]);
        // printf("%c %d %d ha hb//\n", s[o], ha, hb);

        if (dd == 0 || t == um.end() || t->second.first <= 0) {
            char w = dq.front();
            dq.pop_front();
            rev.push_back(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++;
        }
        else break;
    }

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

    // printf("di : %d, dd : %d\n", di, dd);
    if (r1 == sa && r2 == sb) {
        // printf("%d %d // :pass\n", di, dd);
        flag = max(flag, (di - dd + 1) * 2 + dd);
    }
    for (int i : v[o])
        if (i != pa && !visit[i])
            cal(i, o, di + 1, dd, h1, h2, r1, r2, s1, s2);

    while (!rev.empty()) {
        dq.push_front(rev.back());
        rev.pop_back();
    }

    dq.pop_back();
    um[th].first++;
}

// o가 포함된 센트로이드를 찾아라.
// 이제 센트로이드에서 구해야하는데..
// 해싱을 잘 써야함.
// 이분탐색시 초기화 잘해줘야함

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

    // printf("%d %d\n", o, t);

    pcal(t, t, 0, -s[t], -s[t]);
    cal(t, t, 0, 0, 0, 0, 0, 0, 0, 0);
    dq.clear();
    um.clear();
    // printf("//%d//\n", flag);

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

    // 훌수팰린.
    // 길이= mid * 2 + 1

    /*
    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 = 0, 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);
    */

    go(0);
    printf("%d", flag);
}

Compilation message (stderr)

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