oj.uz

Submission #202730

# Submission time Handle Problem Language Result Execution time Memory
202730 2020-02-17T21:07:14 Z rdd6584 Lampice (COCI19_lampice) C++14
17 / 110
 5000 ms 12028 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[50002][2];
int dh[50002][2];
int rh[50002][2];
int pal[50002];
vector<int> v[50002];

map<ll, int> um;
int rotn[50002];
char visit[50002];
char s[50002];
int ha, hb;

vector<int> road;
int len, flag, ans = 1;

int pre(int o, int pa) {
    int ret = 1;
    pal[o] = 0;
    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) {
    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[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);
    }
}

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

    rh[o][0] = (rh[pa][0] + rhq[n - di][0] * s[o]) % pr[0];
    rh[o][1] = (rh[pa][1] + rhq[n - di][1] * s[o]) % pr[1];

    if (rh[o][0] == dh[o][0] * rhq[n - di][0] % pr[0] &&
        rh[o][1] == dh[o][1] * rhq[n - di][1] % pr[1])
        pal[o] = 1;

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

void cal(int o, int pa, int di) {
    road.push_back(o);
    int p = 2 * di + 1 - len;

    if (sz(road) > p && p >= 0 && pal[road[p]]) {
        ha = (dh[o][0] - dh[road[p]][0] + pr[0]) * rhq[n - di][0] % pr[0];
        hb = (dh[o][1] - dh[road[p]][1] + pr[1]) * rhq[n - di][1] % pr[1];

        if (um.find(ha * pr[1] + hb) != um.end() && um[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);

    road.pop_back();
}

void go(int o) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    visit[t]++;
    um.clear();
    um[0] = 100000;
    preHash(t, 50001, 0);

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

    road.push_back(t);
    for (int &i : v[t])
        if (!visit[i] && !flag) {
            pl(i, t, 1, 0, 0, -1);
            cal(i, t, 1);
            pl(i, t, 1, 0, 0, 1);
        }
    road.pop_back();

    for (int &i : v[t])
        if (!visit[i] && !flag)
            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++) {
        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);
    }

    int l = 1, r = (n - 1) / 2, mid;
    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, r * 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, 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:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:136: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 1528 KB Output is correct
2 Correct 21 ms 1528 KB Output is correct
3 Correct 76 ms 1784 KB Output is correct
4 Correct 86 ms 1784 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4134 ms 10104 KB Output is correct
2 Correct 4975 ms 10360 KB Output is correct
3 Correct 3658 ms 11000 KB Output is correct
4 Correct 4728 ms 11524 KB Output is correct
5 Execution timed out 5053 ms 12028 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 9080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1528 KB Output is correct
2 Correct 21 ms 1528 KB Output is correct
3 Correct 76 ms 1784 KB Output is correct
4 Correct 86 ms 1784 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 4134 ms 10104 KB Output is correct
9 Correct 4975 ms 10360 KB Output is correct
10 Correct 3658 ms 11000 KB Output is correct
11 Correct 4728 ms 11524 KB Output is correct
12 Execution timed out 5053 ms 12028 KB Time limit exceeded
13 Halted 0 ms 0 KB -