oj.uz

답안 #526569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526569 2022-02-15T09:23:40 Z tht2005 Lampice (COCI19_lampice) C++17
17 / 110
 4267 ms 11644 KB 
#include <bits/stdc++.h>

using namespace std;

int rd() {
    bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
    int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
    return neg ? -n : n;
}
void wr(int n) {
    static char o[11];
    if(n < 0) putchar('-'), n = -n;
    int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
    while(i--) putchar(o[i]);
}

typedef unsigned long long LL;

const int N = 50005;
const int B = 311;
const int LG = 16;
int n, res;
char s[N];
vector<int> aj[N];

struct sub1 {
    void dfs(int v, int p_, int d, LL pw, LL up, LL down) {
        if(up == down && res < d)
            res = d;
        for(int u : aj[v]) {
            if(u == p_) continue;
            dfs(u, v, d + 1, pw * B, up + pw * s[u], down * B + s[u]);
        }
    }
    sub1() {
        for(int i = 1; i <= n; ++i)
            dfs(i, -1, 1, B, s[i], s[i]);
    }
};
struct sub4 {
    int sz[N], dep[N], p[N][LG];
    bool r[N], pal[N];
    LL up[N], down[N], pw[N];
    void dfs(int v, int p_) {
        sz[v] = 1;
        for(int u : aj[v]) {
            if(u == p_ || r[u]) continue;
            dfs(u, v);
            sz[v] += sz[u];
        }
    }
    int find_centroid(int v, int p_, int e) {
        for(int u : aj[v]) {
            if(u == p_ || r[u]) continue;
            if(sz[u] > e) return find_centroid(u, v, e);
        }
        return v;
    }
    int getup(int v, int dd) {
        for(int i = LG; i--; )
            if(dd >> i & 1)
                v = p[v][i];
        return v;
    }
    set<LL> S;
    bool go(int v, int p_, int L, bool o) {
        if(dep[v] > L) return 0;
        pal[v] = (down[v] == up[v]);
        if(o) {
            S.insert(down[v]);
        }
        else {
            p[v][0] = p_;
            for(int i = 0; i + 1 < LG; ++i)
                if(p[v][i] < 0) p[v][i + 1] = -1;
                else p[v][i + 1] = p[p[v][i]][i];
            int dd = L - dep[v] + 1;
            if(dd <= dep[v]) {
                int x = getup(v, dd - 1);
                if(pal[x]) {
                    x = p[x][0];
                    if(S.count(down[v] - down[x] * pw[dep[v] - dep[x]]))
                        return 1;
                }
            }
        }
        for(int u : aj[v]) {
            if(u == p_ || r[u]) continue;
            if(!o) {
                dep[u] = dep[v] + 1;
                up[u] = up[v] + pw[dep[v]] * s[u];
                down[u] = down[v] * B + s[u];
            }
            if(go(u, v, L, o))
                return 1;
        }
        return 0;
    }
    bool solve(int v, int L) {
        dfs(v, -1);
        v = find_centroid(v, -1, sz[v] >> 1);
        r[v] = 1;
        S.clear();
        S.insert(s[v]);
        pal[v] = 1;
        dep[v] = 1;
        up[v] = down[v] = s[v];
        for(int u : aj[v]) {
            if(r[u]) continue;
            dep[u] = dep[v] + 1;
            up[u] = up[v] + pw[dep[v]] * s[u];
            down[u] = down[v] * B + s[u];
            if(go(u, v, L, 0))
                return 1;
            go(u, v, L, 1);
        }
        for(int u : aj[v])
            if(!r[u] && solve(u, L))
                return 1;
        return 0;
    }
    bool ck(int L) {
        if(L <= n) {
            for(int i = 1; i <= n; ++i)
                r[i] = 0;
            return solve(1, L);
        }
        return 0;
    }
    sub4() {
        pw[0] = 1;
        for(int i = 1; i < N; ++i)
            pw[i] = pw[i - 1] * B;
        for(int par = 0; par < 2; ++par) {
            int ll = 1, rr = n;
            while(ll <= rr) {
                int m = (ll + rr) >> 1, L = m << 1 | par;
                if(ck(L)) {
                    if(res < L) res = L;
                    ll = m + 1;
                }
                else
                    rr = m - 1;
            }
        }
    }
};

int main() {
    scanf("%d %s", &n, s + 1);
    for(int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        aj[u].push_back(v);
        aj[v].push_back(u);
    }
    res = 1;
    if(n <= 3000)
        delete new sub1;
    else
        delete new sub4;
    wr(res);
    return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%d %s", &n, s + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1356 KB Output is correct
2 Correct 10 ms 1484 KB Output is correct
3 Correct 56 ms 1484 KB Output is correct
4 Correct 125 ms 1552 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1476 KB Output is correct
7 Correct 2 ms 1468 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1973 ms 11644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4267 ms 11464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1356 KB Output is correct
2 Correct 10 ms 1484 KB Output is correct
3 Correct 56 ms 1484 KB Output is correct
4 Correct 125 ms 1552 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1476 KB Output is correct
7 Correct 2 ms 1468 KB Output is correct
8 Incorrect 1973 ms 11644 KB Output isn't correct
9 Halted 0 ms 0 KB -