답안 #289946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289946 2020-09-03T08:55:32 Z pichulia Lampice (COCI19_lampice) C++17
110 / 110
3273 ms 19192 KB
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<math.h>
#include<map>
#include<time.h>
#include<assert.h>
using namespace std;
using lld = long long int;
using pll = pair<long long int, long long int>;
using pii = pair<int, int>;
using pil = pair<int, long long int>;
using pli = pair<long long int, int>;
using piii = pair<pii, int>;
using lf = double;
using pff = pair<lf, lf>;
int n;
char a[50009];
bool centmark[50009];
vector<int> v[50009];
int sz[50009];
int dd[50009];
void getsz(int si, int pi) {
    int i, j, k;
    sz[si] = 1;
    for (i = 0; i < v[si].size(); i++) {
        j = v[si][i];
        if (j == pi)continue;
        if (centmark[j])continue;
        getsz(j, si);
        sz[si] += sz[j];
    }
}
int getcent(int si) {
    int pi = -1;
    int size = sz[si];
    while (1) {
        bool done = true;
        for (int i = 0; i < v[si].size(); i++) {
            int j = v[si][i];
            if (j == pi)continue;
            if (centmark[j])continue;
            if (sz[j] * 2 > size) {
                pi = si;
                si = j;
                done = false;
                break;
            }
        }
        if (done)break;
    }
    return si;
}
lld expp(lld p, lld q, lld m) {
    lld r = 1;
    lld z = p % m;
    while (q) {
        if (q & 1) { r = (r * z) % m; }
        q >>= 1;
        if (q) { z = (z * z) % m; }
    }
    return r;
}
int result = 1;
struct Hash {
    const static int HM = 5;
    int v[HM];
    static int M[HM];
    static int x[HM];
    static int rx[HM];
    Hash() {
        for (int i = 0; i < HM; i++) { v[i] = 0; }
    }
    void push(char z) {
        for (int i = 0; i < HM; i++) {
            v[i] = (1LL * v[i] * x[i] + z) % M[i];
        }
    }
    void rpush(char z) {
        for (int i = 0; i < HM; i++) {
            v[i] = (1LL * v[i] * rx[i] + z) % M[i];
        }
    }
    bool operator != (const Hash& z)const {
        for (int i = 0; i < HM; i++) {
            if (v[i] != z.v[i])return true;
        }
        return false;
    }
    bool operator == (const Hash& z)const {
        for (int i = 0; i < HM; i++) {
            if (v[i] != z.v[i])return false;
        }
        return true;
    }
    bool operator <(const Hash& z)const {
        for (int i = 0; i < HM; i++) {
            if (v[i] - z.v[i])return v[i] < z.v[i];
        }
        return false;
    }
    Hash shift(int z) const {
        Hash res;
        for (int i = 0; i < HM; i++) {
            lld diff = 1;
            if (z > 0) {
                diff = expp(x[i], z, M[i]);
            }
            else {
                diff = expp(rx[i], -z, M[i]);
            }
            res.v[i] = (1LL * v[i] * diff) % M[i];
        }
        return res;
    }
    Hash operator -(const Hash& z)const {
        Hash res;
        for (int i = 0; i < HM; i++) {
            res.v[i] = (v[i] - z.v[i]) % M[i];
            if (res.v[i] < 0)res.v[i] += M[i];
        }
        return res;
    }
    void print() {
        printf("{ ");
        for (int i = 0; i < HM; i++) {
            printf("%d, ", v[i]);
        }
        printf("}\n");
    }
};
int Hash::M[Hash::HM] = {
    //    1000000007,1000000009, 998244353, 1000100161, 1000100173,
        1000100183, 1000100201, 1000100239, 1000100279,1000100303,
        //1428571429,
};
int Hash::x[Hash::HM] = { };
int Hash::rx[Hash::HM] = { };

struct A {
    int head;
    int len;
    Hash h;
    Hash rh;
    A() { len = 0; head = -1; }
    A operator+(char z) const {
        A res;
        res.head = head;
        res.h = h;
        res.rh = rh;

        res.len = len + 1;
        res.h.push(z);
        res.rh.rpush(z);
        return res;
    }
    bool operator <(const A& z)const {
        if (len - z.len)return len < z.len;
        if (head - z.head) return head < z.head;
        if (h != z.h) return h < z.h;
        return rh < z.rh;
    }
};
A b[50009];
A c[50009];
int blist[50009];
int clist[50009];
int bl;
int cl;
vector<int> vd[50009];
int dmax_1;
int dmax_2;
void build(int dep, int si, int pi) {
    int i, j;
    dd[si] = dep;
    vd[dep].push_back(si);

    if (dmax_2 < dep) {
        dmax_2 = dep;
        if (dmax_1 < dmax_2) {
            swap(dmax_1, dmax_2);
        }
    }

    blist[bl++] = si;
    if (dep == 0) {
        b[si] = A();
        b[si].len = 1;
        b[si].h.push(a[si]);
        b[si].rh.rpush(a[si]);
        c[si] = A();
    }
    else {
        b[si] = b[pi] + a[si];
        c[si] = c[pi] + a[si];
        if (dep == 1) {
            b[si].head = si;
            c[si].head = si;
        }
    }
    for (i = 0; i < v[si].size(); i++) {
        j = v[si][i];
        if (j == pi)continue;
        if (centmark[j])continue;
        build(dep + 1, j, si);
    }
}


Hash bb[50009];
Hash cc[50009];
int ch[50009];
bool valid(int len) {
    //printf("len : %d, dmax_1 : %d\n", len, dmax_1);
    int i, j, k;
    int di, ei;
    int dsi = max(0, len - dmax_1 - 1);
    int dei = min(dmax_1, len - 1);
    // (ph * x + qr) * x^(ei-1) = (pr + qh * x) * x^(di)
    // ph * x^ ei - pr * x ^ di == qh * x ^ (di + 1) - qr * x ^ (ei - 1)
    cl = 0;
    for (i = 0; i < bl; i++) {
        int qi = blist[i];
        int di = dd[qi];
        int ei = len - di - 1;
        if (di >= dsi && di <= dei) {
            clist[cl++] = blist[i];
            bb[qi] = b[qi].h - b[qi].rh.shift(len - 1);
            cc[qi] = c[qi].h - c[qi].rh.shift(len - 1);
        }
        /*
        printf("about %d\n", qi);
        printf("%d %d\n", di, ei);
        printf("%d %d\n", b[qi].len, b[qi].head);
        b[qi].h.print();
        b[qi].rh.print();
        printf("%d %d\n", c[qi].len, c[qi].head);
        c[qi].h.print();
        c[qi].rh.print();

        bb[qi].print();
        cc[qi].print();
        */
    }
    sort(clist, clist + cl, [](int i, int j) {
        if (c[i].len - c[j].len)return c[i].len < c[j].len;
        if (cc[i] != cc[j])return cc[i] < cc[j];
        return c[i].head < c[j].head;
        });
    k = 0;
    ch[k] = 0;
    for (i = 0; i < cl;) {
        for (j = i; j < cl; j++) {
            if (c[clist[j]].len != k) {
                break;
            }
        }
        ch[k + 1] = j;
        k++;
        i = j;
    }
    for (di = dsi; di <= dei; di++) {
        ei = len - di - 1;
        // check b where dep == di and check c where dep == ci
        if (ei < 0 || ei >= k || ch[ei] == ch[ei + 1])continue;
        for (auto bi : vd[di]) {
            Hash& me = bb[bi];
            int bhead = b[bi].head;
            int l, r;
            l = ch[ei];
            r = ch[ei + 1];
            while (l < r) {
                int m = (l + r) / 2;
                int mi = clist[m];
                if (cc[mi] < me) l = m + 1;
                else r = m;
            }
            if (l < ch[ei + 1] && cc[clist[l]] == me) {
                if (c[clist[l]].head == bhead) {
                    if (ch[ei + 1] - l < 10) {
                        l++;
                        for (; l < ch[ei + 1]; l++) {
                            if (cc[clist[l]] != me)break;
                            if (c[clist[l]].head != bhead)return true;
                        }
                    }
                    else {
                        int ll = l + 1;
                        int rr = ch[ei + 1];
                        while (ll < rr) {
                            int mm = (ll + rr) / 2;
                            int mi = clist[mm];
                            if (me < cc[mi]) { rr = mm; }
                            else if (c[mi].head == bhead) { ll = mm + 1; }
                            else return true;
                        }
                        if (ll < ch[ei + 1] && cc[clist[ll]] == me) {
                            if (c[clist[ll]].head != bhead)return true;
                        }
                    }
                }
                else {
                    return true;
                }
            }
        }
    }
    return false;
}
void process(int si) {
    getsz(si, -1);
    if (sz[si] <= result)return;
    si = getcent(si);

    centmark[si] = true;
    for (int i = 0; i < v[si].size(); i++) {
        int j = v[si][i];
        if (centmark[j])continue;
        process(j);
    }
  centmark[si] = false;
    bl = 0;
    dmax_1 = dmax_2 = 0;
    build(0, si, -1);

    int l, r;
    // odd
    l = result + 1;
    r = dmax_1 + dmax_2 + 2;
    l = l / 2;
    r = r / 2;
    if (l < r && valid(l * 2 + 1)) {
        result = l * 2 + 1;
        l++;
        while (l < r) {
            int mid = (l + r) / 2;
            if (valid(mid * 2 + 1)) {
                //printf("centroid %d : mid %d success!!\n", si, mid);
                if (result < mid * 2 + 1)result = mid * 2 + 1;
                l = mid + 1;
            }
            else {
                //printf("centroid %d : mid %d fail\n", si, mid);
                r = mid;
            }
        }
    }
    // even
    l = result + 1;
    r = dmax_1 + dmax_2 + 2;
    l = (l + 1) / 2;
    r = (r + 1) / 2;
    if (l < r && valid(2 * l)) {
        result = 2 * l;
        l++;
        while (l < r) {
            int mid = (l + r) / 2;
            if (valid(mid * 2)) {
                //printf("centroid %d : mid %d success!!\n", si, mid);
                if (result < mid * 2)result = mid * 2;
                l = mid + 1;
            }
            else {
                //printf("centroid %d : mid %d fail\n", si, mid);
                r = mid;
            }
        }
    }

    for (int i = 0; i <= dmax_1; i++) {
        vd[i].clear();
    }

}
void inil() {
    for (int i = 0; i < Hash::HM; i++) {
        Hash::x[i] = 257679;
        Hash::rx[i] = expp(Hash::x[i], Hash::M[i] - 2, Hash::M[i]);
    }
}
int main() {
    inil();
    int i, j, k, l;
    int t = 1, tv = 0;
    while (t--) {
        scanf("%d", &n);
        scanf("%s", a);
        a[0] ^= 73;
        for (i = 1; i < n; i++) {
            a[i] ^= 73;
            scanf("%d %d", &j, &k);
            j--; k--;
            v[j].push_back(k);
            v[k].push_back(j);
        }
        process(0);
        printf("%d\n", result);
    }
}

Compilation message

lampice.cpp: In function 'void getsz(int, int)':
lampice.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (i = 0; i < v[si].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
lampice.cpp:29:15: warning: unused variable 'k' [-Wunused-variable]
   29 |     int i, j, k;
      |               ^
lampice.cpp: In function 'int getcent(int)':
lampice.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < v[si].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
lampice.cpp: In function 'void build(int, int, int)':
lampice.cpp:206:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |     for (i = 0; i < v[si].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
lampice.cpp: In function 'bool valid(int)':
lampice.cpp:230:13: warning: unused variable 'ei' [-Wunused-variable]
  230 |         int ei = len - di - 1;
      |             ^~
lampice.cpp: In function 'void process(int)':
lampice.cpp:321:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  321 |     for (int i = 0; i < v[si].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:388:18: warning: unused variable 'l' [-Wunused-variable]
  388 |     int i, j, k, l;
      |                  ^
lampice.cpp:389:16: warning: unused variable 'tv' [-Wunused-variable]
  389 |     int t = 1, tv = 0;
      |                ^~
lampice.cpp:391:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  391 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
lampice.cpp:392:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  392 |         scanf("%s", a);
      |         ~~~~~^~~~~~~~~
lampice.cpp:396:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  396 |             scanf("%d %d", &j, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9376 KB Output is correct
2 Correct 10 ms 9344 KB Output is correct
3 Correct 35 ms 9472 KB Output is correct
4 Correct 38 ms 9472 KB Output is correct
5 Correct 6 ms 9344 KB Output is correct
6 Correct 6 ms 9344 KB Output is correct
7 Correct 6 ms 9344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 312 ms 17100 KB Output is correct
2 Correct 2636 ms 17632 KB Output is correct
3 Correct 1420 ms 18296 KB Output is correct
4 Correct 1530 ms 18788 KB Output is correct
5 Correct 3273 ms 19064 KB Output is correct
6 Correct 561 ms 19192 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 414 ms 13944 KB Output is correct
2 Correct 1156 ms 14072 KB Output is correct
3 Correct 1349 ms 14968 KB Output is correct
4 Correct 2351 ms 15456 KB Output is correct
5 Correct 1647 ms 13944 KB Output is correct
6 Correct 507 ms 13556 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9376 KB Output is correct
2 Correct 10 ms 9344 KB Output is correct
3 Correct 35 ms 9472 KB Output is correct
4 Correct 38 ms 9472 KB Output is correct
5 Correct 6 ms 9344 KB Output is correct
6 Correct 6 ms 9344 KB Output is correct
7 Correct 6 ms 9344 KB Output is correct
8 Correct 312 ms 17100 KB Output is correct
9 Correct 2636 ms 17632 KB Output is correct
10 Correct 1420 ms 18296 KB Output is correct
11 Correct 1530 ms 18788 KB Output is correct
12 Correct 3273 ms 19064 KB Output is correct
13 Correct 561 ms 19192 KB Output is correct
14 Correct 414 ms 13944 KB Output is correct
15 Correct 1156 ms 14072 KB Output is correct
16 Correct 1349 ms 14968 KB Output is correct
17 Correct 2351 ms 15456 KB Output is correct
18 Correct 1647 ms 13944 KB Output is correct
19 Correct 507 ms 13556 KB Output is correct
20 Correct 666 ms 12688 KB Output is correct
21 Correct 612 ms 12528 KB Output is correct
22 Correct 1561 ms 12792 KB Output is correct
23 Correct 499 ms 12800 KB Output is correct
24 Correct 1070 ms 14440 KB Output is correct
25 Correct 1031 ms 13816 KB Output is correct
26 Correct 1574 ms 15340 KB Output is correct
27 Correct 440 ms 12872 KB Output is correct
28 Correct 435 ms 12920 KB Output is correct
29 Correct 482 ms 13048 KB Output is correct
30 Correct 1994 ms 15352 KB Output is correct
31 Correct 1060 ms 13688 KB Output is correct
32 Correct 1684 ms 15608 KB Output is correct
33 Correct 433 ms 12628 KB Output is correct