Submission #643519

#	Time	Username	Problem	Language	Result	Execution time	Memory
643519		mychecksedad	Palindromi (COCI22_palindromi)	C++17	30 / 110	79 ms	95436 KiB

Main

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

ll e[N], re[N], h[N], rh[N];
ll po(ll a, ll b){ll res = 1; while(b){if(b&1) (res*=a)%=MOD; b>>=1; (a*=a)%=MOD;} return res;}
struct Dsu {
    vector<int> s, p;
    vector<deque<char>> str;
    vector<ll> ans;
    vector<set<int>> hashes, hashes1;
    Dsu(int n, string ss){
        s.resize(n+1, 1);
        p.resize(n+1);
        hashes.resize(n+1);
        hashes1.resize(n+1);
        ans.resize(n+1, 1);
        for(int i = 0; i <= n; ++i) p[i] = i;
        str.pb({'c'});
        for(int i = 0; i < n; ++i) str.pb({ss[i]}), hashes1[i + 1].insert((ss[i] - '0' + 1) * e[1]);
    }
    int find(int v){
        if(p[v] == v) return v;
        return (p[v] = find(p[v]));
    }
    ll merge(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            int f = s[a];
            if(s[a] > s[b]){
                for(char c: str[b]) str[a].pb(c);
                for(int x: hashes[b]) hashes[a].insert(x);
                for(int x: hashes1[b]) hashes1[a].insert(x);
                swap(a, b);
            }else{
                for(int c = str[a].size() - 1; c >= 0; --c) str[b].push_front(str[a][c]);
                for(int x: hashes[a]) hashes[b].insert(x);
                for(int x: hashes1[a]) hashes1[b].insert(x);
            }
            s[b] += s[a];
            p[a] = b;
            int x = p[a];
            ans[x] = 0;

            h[0] = 0, rh[s[x] + 1] = 0;
            for(int i = 1; i <= s[x]; ++i) h[i] = (h[i - 1] + e[i] * (str[x][i-1]-'0'+1)) % MOD;
            for(int i = s[x]; i >= 1; --i) rh[i] = (rh[i + 1] + e[s[x] - i + 1] * (str[x][i-1]-'0'+1)) % MOD;

            for(int i = 1; i <= f; ++i){
                // cout << str[x][i - 1];
                for(int j = f + 1; j <= str[x].size(); ++j){
                    int m = (i + j) >> 1;

                    bool ok = 1;

                    int has;

                    if((i - j) & 1){
                        ok = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD) == ((rh[m + 1] - rh[j + 1] + MOD) * re[s[x] - j] % MOD);
                        has = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD);
                    }else{
                        ok = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD) == ((rh[m] - rh[j + 1] + MOD) * re[s[x] - j] % MOD);
                        has = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD);
                    }

                    if(ok) if((i-j)&1) hashes[x].insert(has); else hashes1[x].insert(has);
                }
            }
            return ans[x] = hashes[x].size() + hashes1[x].size();
        }
        return -1;
    }
};


int n;
string s;
void solve(){
    cin >> n >> s;

    e[0] = re[0] = 1;
    for(int i = 1; i < N; ++i) e[i] = (e[i - 1] * 31) % MOD;
    re[N - 1] = po(e[N - 1], MOD - 2);
    for(int i = N - 2; i >= 0; --i) re[i] = (re[i + 1] * 31) % MOD; 
    Dsu d(n, s);
    if(n <= 1000){
        for(int i = 0; i < n - 1; ++i){
            int u, v; cin >> u >> v;
            u = d.find(u);
            v = d.find(v);
            cout << d.merge(u, v) << '\n';
        }
    }


}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

Main.cpp: In member function 'll Dsu::merge(int, int)':
Main.cpp:62:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for(int j = f + 1; j <= str[x].size(); ++j){
      |                                    ~~^~~~~~~~~~~~~~~~
Main.cpp:77:23: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   77 |                     if(ok) if((i-j)&1) hashes[x].insert(has); else hashes1[x].insert(has);
      |                       ^
Main.cpp: In function 'int main()':
Main.cpp:115:16: warning: unused variable 'aa' [-Wunused-variable]
  115 |     int T = 1, aa;
      |                ^~

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