Submission #684436

#	Time	Username	Problem	Language	Result	Execution time	Memory
684436		ghostwriter	Palindromi (COCI22_palindromi)	C++17	110 / 110	379 ms	77784 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define bg begin
#define ed end
#define ft front
#define bk back
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ers erase
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
#define mtp make_tuple
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define str string
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const int oo = 1e9 + 5;
const pi M = {1e9 + 7, 1e9 + 9};
const pi base = {37, 127};
const int N = 1e5 + 5;
int n, a[N], p[N], lm[N], rm[N], nxt[N], pos[N], len[N], len1[N], LOG[N];
pi e[N], h[N], h1[N], P[N], c[N][17], c1[N][17], posl[N], posr[N];
vi a1;
set<pi> s[N];
int getp(int x) { return x == p[x]? x : p[x] = getp(p[x]); }
void join(int x, int y) {
    int px = getp(x), py = getp(y);
    p[py] = px;
    nxt[rm[px]] = lm[py];
    rm[px] = rm[py];
}
void trans() {
    FRN(i, n) {
        p[i] = lm[i] = rm[i] = i;
        nxt[i] = -1;
    }
    FRN(i, n - 1) join(e[i].st, e[i].nd);
    int fp = lm[getp(0)];
    WHILE(fp != -1) {
        a1.pb(fp);
        fp = nxt[fp];
    }
    FRN(i, n) pos[a1[i]] = i;
    vi a2(n);
    FRN(i, n) a2[i] = a[i];
    FRN(i, n) a[pos[i]] = a2[i];
}
void buildh() {
    FRN(i, n) {
        h[i].st = (1LL * (i? h[i - 1].st : 0) * base.st + a[i] + 1) % M.st;
        h[i].nd = (1LL * (i? h[i - 1].nd : 0) * base.nd + a[i] + 1) % M.nd;
    }
    FSN(i, n) {
        h1[i].st = (1LL * (i + 1 < n? h1[i + 1].st : 0) * base.st + a[i] + 1) % M.st;
        h1[i].nd = (1LL * (i + 1 < n? h1[i + 1].nd : 0) * base.nd + a[i] + 1) % M.nd;
    }
    P[0] = {1, 1};
    FOR(i, 1, n) {
        P[i].st = 1LL * P[i - 1].st * base.st % M.st;
        P[i].nd = 1LL * P[i - 1].nd * base.nd % M.nd;
    }
}
pi get(int l, int r) {
    pi ans;
    ans.st = (h[r].st - 1LL * (l? h[l - 1].st : 0) * P[r - l + 1].st % M.st + M.st) % M.st;
    ans.nd = (h[r].nd - 1LL * (l? h[l - 1].nd : 0) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
    return ans;
}
pi get1(int l, int r) {
    pi ans;
    ans.st = (h1[l].st - 1LL * (r + 1 < n? h1[r + 1].st : 0) * P[r - l + 1].st % M.st + M.st) % M.st;
    ans.nd = (h1[l].nd - 1LL * (r + 1 < n? h1[r + 1].nd : 0) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
    return ans;
}
bool check(int l, int r) { return get(l, r) == get1(l, r); }
void buildp() {
    FRN(i, n) {
        int l = 0, r = min(i, n - 1 - i);
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (check(i - mid, i + mid)) {
                len[i] = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
    }
    len1[n - 1] = -1;
    FRN(i, n - 1) {
        len1[i] = -1;
        if (a[i] != a[i + 1]) continue;
        int l = 0, r = min(i, n - 2 - i);
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (check(i - mid, i + 1 + mid)) {
                len1[i] = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
    }
}
pi best(const pi &a, const pi &b) { return {min(a.st, b.st), max(a.nd, b.nd)}; }
void buildstb() {
    FRN(i, n) {
        c1[i][0] = {oo, -oo};
        c[i][0] = {i - len[i], i + len[i]};
        if (len1[i] != -1) c1[i][0] = {i - len1[i], i + 1 + len1[i]};
    }
    FOR(j, 1, 16)
    FRN(i, n) {
        if (i + (1 << j) - 1 >= n) break;
        c[i][j] = best(c[i][j - 1], c[i + (1 << (j - 1))][j - 1]);
        c1[i][j] = best(c1[i][j - 1], c1[i + (1 << (j - 1))][j - 1]);
    }
    FOR(i, 1, n) LOG[i] = log2(i);
}
void buildplr() {
    FRN(i, n) {
        int l = 0, r = i;
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (mid - i + mid >= 0) {
                posl[i].st = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        l = 0; r = i - 1;
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (mid - i + mid + 1 >= 0) {
                posl[i].nd = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
    }
    FRN(i, n) {
        int l = 0, r = i;
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (mid + mid <= i) {
                posr[i].st = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        l = 0; r = i - 1;
        WHILE(l <= r) {
            int mid = l + (r - l) / 2;
            if (mid + mid + 1 <= i) {
                posr[i].nd = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
    }
}
pi getc(int l, int r) {
    int len = LOG[r - l + 1];
    return best(c[l][len], c[r - (1 << len) + 1][len]);
}
pi getc1(int l, int r) {
    int len = LOG[r - l + 1];
    return best(c1[l][len], c1[r - (1 << len) + 1][len]);
}
pi getl(int l, int r) {
    int tmpp = l + posl[r - l].st, ln = tmpp, rn = r;
    pi ans = {oo, oo};
    WHILE(ln <= rn) {
        int mid = ln + (rn - ln) / 2;
        pi tmp = getc(tmpp, mid);
        if (tmp.nd >= r) {
            ans = min(ans, {mid, 0});
            rn = mid - 1;
        }
        else ln = mid + 1;
    }
    if (l == r) return ans;
    tmpp = l + posl[r - l].nd; ln = tmpp; rn = r - 1;
    WHILE(ln <= rn) {
        int mid = ln + (rn - ln) / 2;
        if (mid - r + mid + 1 < l) {
            ln = mid + 1;
            continue;
        }
        pi tmp = getc1(tmpp, mid);
        if (tmp.nd >= r) {
            ans = min(ans, {mid, 1});
            rn = mid - 1;
        }
        else ln = mid + 1;
    }
    return ans;
}
pi getr(int l, int r) {
    int tmpp = l + posr[r - l].st, ln = l, rn = tmpp;
    pi ans = {0, 0};
    WHILE(ln <= rn) {
        int mid = ln + (rn - ln) / 2;
        pi tmp = getc(mid, tmpp);
        if (tmp.st <= l) {
            ans = max(ans, {mid, 0});
            ln = mid + 1;
        }
        else rn = mid - 1;
    }
//    cerr << l << ' ' << r << " : " << tmpp << ' ' << ans.st << " : " << getc(4, 4).st << '\n';
    if (l == r) return ans;
    tmpp = l + posr[r - l].nd; ln = l; rn = tmpp;
    WHILE(ln <= rn) {
        int mid = ln + (rn - ln) / 2;
        if (mid + 1 + mid - l > r) {
            rn = mid - 1;
            continue;
        }
        pi tmp = getc1(mid, tmpp);
        if (tmp.st <= l) {
            ans = max(ans, {mid, 1});
            ln = mid + 1;
        }
        else rn = mid - 1;
    }
    return ans;
}
void debug(const set<pi> &s) {
    EACH(i, s) {
        cerr << i.st << ' ' << i.nd << '\n';
    }
    cerr << '\n';
}
void join1(int x, int y) {
    int px = getp(x), py = getp(y);
//    cerr << lm[px] << ' ' << rm[px] << " - " << lm[py] << ' ' << rm[py] << '\n';
    if (rm[px] - lm[px] > rm[py] - lm[py]) {
        FOR(i, lm[py], rm[py]) {
            pi tmp = getl(lm[px], i);
            s[px].ins(get(tmp.st - i + tmp.st + tmp.nd, i));
//            cerr << tmp.st - i + tmp.st + tmp.nd << ' ' << i << '\n';
//            cerr << get(tmp.st - i + tmp.st + tmp.nd, i).st << '\n';
        }
        p[py] = px;
        rm[px] = rm[py];
    }
    else {
        FOR(i, lm[px], rm[px]) {
            pi tmp = getr(i, rm[py]);
            s[py].ins(get(i, tmp.st + tmp.st - i + tmp.nd));
//            cerr << i << ' ' << tmp.st + tmp.st - i + tmp.nd << '\n';
//            cerr << get(i, tmp.st + tmp.st - i + tmp.nd).st << '\n';
        }
        p[px] = py;
        lm[py] = lm[px];
    }
//    cerr << '\n';
//    debug(s[py]);
//    cerr << "\n\n";
}
void ansq() {
//    FRN(i, n) cerr << a[i];
//    cerr << "\n\n";
//    cerr << getr(0, 5).st << '\n';
//    exit(0);
    FRN(i, n) {
        p[i] = i;
        lm[i] = rm[i] = pos[i];
        s[i].ins(get(pos[i], pos[i]));
    }
    FRN(i, n - 1) {
        join1(e[i].st, e[i].nd);
        cout << sz(s[getp(e[i].st)]) << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n;
    FRN(i, n) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    FRN(i, n - 1) {
        cin >> e[i].st >> e[i].nd;
        --e[i].st;
        --e[i].nd;
    }
    trans();
    buildh();
    buildp();
    buildstb();
    buildplr();
    ansq();
    return 0;
}
/*
8
00011010
1 2
2 3
3 4
4 5
5 6
6 7
7 8

8
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 2

*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50