Submission #847201

#	Time	Username	Problem	Language	Result	Execution time	Memory
847201		Pacybwoah	Palindromi (COCI22_palindromi)	C++17	10 / 110	1038 ms	4520 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<string>
using namespace std;
#define ll long long
vector<int> dsu;
const ll mod=998244353;
vector<string> vec;
void build(int n){
    dsu.resize(n+1);
    for(int i=1;i<=n;i++) dsu[i]=i;
}
int query(int x){
    if(x==dsu[x]) return x;
    int tmp=query(dsu[x]);
    dsu[x]=tmp;
    return tmp;
}
void unite(int a,int b){
    a=query(a),b=query(b);
    if(a==b) return;
    vec[a]+=vec[b];
    dsu[b]=a;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    build(n);
    vec.resize(n+1,"");
    for(int i=0;i<n;i++) vec[i+1]+=s[i];
    int a,b;
    vector<ll> bases(1005);
    bases[0]=1;
    for(int i=1;i<1005;i++) bases[i]=bases[i-1]*3%mod;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        unite(a,b);
        string now=vec[query(a)];
        int sz=now.size();
        vector<ll> hash(sz+1),rev(sz+1);
        hash[0]=1,rev[0]=1;
        for(int i=1;i<=sz;i++){
            hash[i]=(hash[i-1]*3%mod+(now[i-1]-'0'+1))%mod;
            rev[i]=(rev[i-1]*3%mod+(now[sz-i]-'0'+1))%mod;
        }
        set<ll> s;
        for(int i=1;i<=sz;i++){
            for(int j=i;j<=sz;j++){
                if((mod+hash[j]-hash[i-1]*bases[j-i+1]%mod)%mod==(mod+rev[sz-i+1]-rev[sz-j]*bases[j-i+1]%mod)%mod){
                    s.insert((mod+hash[j]-hash[i-1]*bases[j-i+1]%mod)%mod);
                }
            }
        }
        cout<<s.size()<<"\n";
        //or(auto x:s) cout<<x<<" ";
    }
}

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