oj.uz

Submission #202841

# Submission time Handle Problem Language Result Execution time Memory
202841 2020-02-18T07:44:53 Z rdd6584 Lampice (COCI19_lampice) C++14
110 / 110
 4075 ms 56868 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];
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);
    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) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    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 = 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:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:147: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 4472 KB Output is correct
2 Correct 17 ms 4728 KB Output is correct
3 Correct 40 ms 5240 KB Output is correct
4 Correct 49 ms 5372 KB Output is correct
5 Correct 7 ms 4264 KB Output is correct
6 Correct 7 ms 4216 KB Output is correct
7 Correct 7 ms 4216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 49320 KB Output is correct
2 Correct 1650 ms 50600 KB Output is correct
3 Correct 1159 ms 51880 KB Output is correct
4 Correct 1419 ms 54188 KB Output is correct
5 Correct 2200 ms 56868 KB Output is correct
6 Correct 321 ms 43512 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3255 ms 50604 KB Output is correct
2 Correct 4075 ms 48556 KB Output is correct
3 Correct 3678 ms 49448 KB Output is correct
4 Correct 3788 ms 40424 KB Output is correct
5 Correct 2716 ms 45096 KB Output is correct
6 Correct 2558 ms 40744 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4472 KB Output is correct
2 Correct 17 ms 4728 KB Output is correct
3 Correct 40 ms 5240 KB Output is correct
4 Correct 49 ms 5372 KB Output is correct
5 Correct 7 ms 4264 KB Output is correct
6 Correct 7 ms 4216 KB Output is correct
7 Correct 7 ms 4216 KB Output is correct
8 Correct 1606 ms 49320 KB Output is correct
9 Correct 1650 ms 50600 KB Output is correct
10 Correct 1159 ms 51880 KB Output is correct
11 Correct 1419 ms 54188 KB Output is correct
12 Correct 2200 ms 56868 KB Output is correct
13 Correct 321 ms 43512 KB Output is correct
14 Correct 3255 ms 50604 KB Output is correct
15 Correct 4075 ms 48556 KB Output is correct
16 Correct 3678 ms 49448 KB Output is correct
17 Correct 3788 ms 40424 KB Output is correct
18 Correct 2716 ms 45096 KB Output is correct
19 Correct 2558 ms 40744 KB Output is correct
20 Correct 1951 ms 28920 KB Output is correct
21 Correct 2177 ms 33920 KB Output is correct
22 Correct 3279 ms 42664 KB Output is correct
23 Correct 869 ms 18040 KB Output is correct
24 Correct 2904 ms 37496 KB Output is correct
25 Correct 2781 ms 35576 KB Output is correct
26 Correct 3325 ms 46632 KB Output is correct
27 Correct 3523 ms 45224 KB Output is correct
28 Correct 2552 ms 28564 KB Output is correct
29 Correct 2686 ms 28908 KB Output is correct
30 Correct 3108 ms 34552 KB Output is correct
31 Correct 2557 ms 30968 KB Output is correct
32 Correct 2270 ms 42444 KB Output is correct
33 Correct 1632 ms 31144 KB Output is correct