Submission #705017

#	Time	Username	Problem	Language	Result	Execution time	Memory
705017		PixelCat	Palindromi (COCI22_palindromi)	C++14	30 / 110	80 ms	31052 KiB

Main

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1010;

struct DSU {
    int p[MAXN];
    void init() {
        memset(p, 0, sizeof(p));
    }
    int find(int n) {
        if(!p[n]) return n;
        return p[n] = find(p[n]);
    }
    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a != b) p[b] = a;
    }
} dsu;

string s[MAXN];
int pos[MAXN];
int res[MAXN];
int pad[MAXN][MAXN];
set<int> st[MAXN];
vector<int> v[MAXN];

const int B = 5;
const int M = 1000000007;
int pw[MAXN];

int owo(int i, int j) {
    if(pad[i][j] != -1) return pad[i][j];
    if(i > j) return pad[i][j] = 1;
    if(res[i] != res[j]) return pad[i][j] = 0;
    return pad[i][j] = owo(i + 1, j - 1);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nya ><
    int n; cin >> n;
    assert(n <= 1000);
    For(i, 1, n) {
        char ch; cin >> ch;
        s[i] = "";
        s[i].push_back(ch);
        pos[i] = 0;
    }
    dsu.init();
    vector<pii> op;
    For(i, 1, n - 1) {
        int a, b; cin >> a >> b;
        a = dsu.find(a); b = dsu.find(b);
        op.eb(a, b);
        pos[b] += sz(s[a]);
        s[a] += s[b];
        dsu.uni(a, b);
    }
    Forr(i, n - 2, 0) {
        auto p = op[i];
        pos[p.S] += pos[p.F];
    }
    int rt = op.back().F;
    pw[0] = 1;
    For(i, 1, n) {
        res[i] = s[rt][i - 1] - '0';
        pos[i]++;
        v[i] = vector<int>(1, pos[i]);
        pw[i] = pw[i - 1] * B % M;
    }
    For(i, 1, n) st[i].insert(res[pos[i]]);

    // For(i, 1, n) cout << res[i];
    // cout << "\n";
    
    memset(pad, -1, sizeof(pad));
    For(i, 1, n) For(j, 1, n) {
        owo(i, j);
    }
    For(i, 1, n) {
        res[i] = (res[i - 1] * B + res[i] + 1) % M;
    }
    auto hsh = [&](int i, int j) {
        return (res[j] - res[i - 1] * pw[j - i + 1] % M + M) % M;
    };
    for(auto &p:op) {
        int a, b;
        tie(a, b) = p;
        for(auto &i:v[a]) for(auto &j:v[b]) {
            if(pad[i][j]) st[a].insert(hsh(i, j));
        }
        for(auto &i:st[b]) st[a].insert(i);
        v[a].insert(v[a].end(), all(v[b]));
        // for(auto &i:st[a]) cout << i << " ";
        // cout << "\n";
        cout << sz(st[a]) << "\n";
    }
    return 0;
}

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