oj.uz

Submission #202843

# Submission time Handle Problem Language Result Execution time Memory
202843 2020-02-18T07:51:00 Z rdd6584 Lampice (COCI19_lampice) C++14
110 / 110
 3587 ms 58796 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4600 KB Output is correct
2 Correct 15 ms 4728 KB Output is correct
3 Correct 39 ms 5368 KB Output is correct
4 Correct 49 ms 5496 KB Output is correct
5 Correct 7 ms 4216 KB Output is correct
6 Correct 7 ms 4216 KB Output is correct
7 Correct 7 ms 4344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1552 ms 51088 KB Output is correct
2 Correct 1952 ms 52392 KB Output is correct
3 Correct 1255 ms 53800 KB Output is correct
4 Correct 1279 ms 56232 KB Output is correct
5 Correct 2039 ms 58796 KB Output is correct
6 Correct 245 ms 45560 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2855 ms 52644 KB Output is correct
2 Correct 3449 ms 50856 KB Output is correct
3 Correct 3514 ms 50984 KB Output is correct
4 Correct 3450 ms 42132 KB Output is correct
5 Correct 2926 ms 46504 KB Output is correct
6 Correct 2597 ms 42080 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4600 KB Output is correct
2 Correct 15 ms 4728 KB Output is correct
3 Correct 39 ms 5368 KB Output is correct
4 Correct 49 ms 5496 KB Output is correct
5 Correct 7 ms 4216 KB Output is correct
6 Correct 7 ms 4216 KB Output is correct
7 Correct 7 ms 4344 KB Output is correct
8 Correct 1552 ms 51088 KB Output is correct
9 Correct 1952 ms 52392 KB Output is correct
10 Correct 1255 ms 53800 KB Output is correct
11 Correct 1279 ms 56232 KB Output is correct
12 Correct 2039 ms 58796 KB Output is correct
13 Correct 245 ms 45560 KB Output is correct
14 Correct 2855 ms 52644 KB Output is correct
15 Correct 3449 ms 50856 KB Output is correct
16 Correct 3514 ms 50984 KB Output is correct
17 Correct 3450 ms 42132 KB Output is correct
18 Correct 2926 ms 46504 KB Output is correct
19 Correct 2597 ms 42080 KB Output is correct
20 Correct 1887 ms 30328 KB Output is correct
21 Correct 2004 ms 35112 KB Output is correct
22 Correct 3162 ms 44328 KB Output is correct
23 Correct 844 ms 18664 KB Output is correct
24 Correct 2303 ms 39160 KB Output is correct
25 Correct 2961 ms 37368 KB Output is correct
26 Correct 3587 ms 48168 KB Output is correct
27 Correct 3109 ms 46888 KB Output is correct
28 Correct 2617 ms 30200 KB Output is correct
29 Correct 2680 ms 30584 KB Output is correct
30 Correct 3290 ms 36216 KB Output is correct
31 Correct 3040 ms 32680 KB Output is correct
32 Correct 2693 ms 44076 KB Output is correct
33 Correct 1677 ms 31784 KB Output is correct