Submission #643504

#	Time	Username	Problem	Language	Result	Execution time	Memory
643504		mychecksedad	Palindromi (COCI22_palindromi)	C++17	10 / 110	1088 ms	66516 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;


struct Dsu {
    vector<int> s, p;
    vector<deque<char>> str;
    vector<ll> ans;
    Dsu(int n, string ss){
        s.resize(n+1, 1);
        p.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]});
    }
    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){
            if(s[a] > s[b]){
                for(char c: str[b]) str[a].pb(c);
                swap(a, b);
            }else{
                for(int c = str[a].size() - 1; c >= 0; --c) str[b].push_front(str[a][c]);
            }
            s[b] += s[a];
            p[a] = b;
            int x = p[a];
            ans[x] = 0;
            set<string> ss, ss1;
            for(int i = 0; i < str[x].size(); ++i){
                for(int j = i; j < str[x].size(); ++j){
                    bool ok = 1;
                    string t = "";
                    for(int k = i; k <= (i + j) / 2; ++k){
                        ok &= str[x][k] == str[x][j - k + i];
                        t += str[x][k];
                    }
                    if(ok) if((i-j)%2) ss.insert(t); else ss1.insert(t);
                }
            }
            return ans[x] = ss.size() + ss1.size();
        }
        return -1;
    }
};


int n;
string s;
void solve(){
    cin >> n >> s;
    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:47:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int i = 0; i < str[x].size(); ++i){
      |                            ~~^~~~~~~~~~~~~~~
Main.cpp:48:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 for(int j = i; j < str[x].size(); ++j){
      |                                ~~^~~~~~~~~~~~~~~
Main.cpp:55:23: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   55 |                     if(ok) if((i-j)%2) ss.insert(t); else ss1.insert(t);
      |                       ^
Main.cpp: In function 'int main()':
Main.cpp:88:16: warning: unused variable 'aa' [-Wunused-variable]
   88 |     int T = 1, aa;
      |                ^~

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