Submission #705013

#	Time	Username	Problem	Language	Result	Execution time	Memory
705013		Cookie197	Palindromi (COCI22_palindromi)	C++17	10 / 110	1069 ms	848 KiB

Main

#pragma GCC optimize("O4,unroll-loops")
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define endl "\n"
#define mp make_pair
#define out(x) cout << #x << " = " << x << endl

int sz[1005], boss[1005], n;
string res[1005];
string arr;

int find(int a){
    if (boss[a] == a) return a;
    return boss[a] = find(boss[a]);
}
void join(int a,int b){
    res[a] += res[b];
    sz[a] += sz[b];
    boss[b] = boss[a];
}

string sub(string s,int i,int j){
    string ans;
    for (int k=i;k<=j;k++) ans += s[k];
    return ans;
}
int work(string s){
    set<string> st;
    int len = s.size();
    for (int i=0;i<len;i++){
        for (int j=1;j<=len;j++){
            if ( (i-j < 0 || i+j >= len) || (s[i-j] != s[i+j])){
                string tmp;
                for (int k=i-j+1;k<=i+j-1;k++) tmp += s[k];
                for (int k=0;k<=(int)tmp.size()/2;k++) st.insert(sub(tmp,k,tmp.size()-k-1));
                break;
            }
        }
    }

    for (int i=0;i<len-1;i++) if (s[i] == s[i+1]){
        for (int j=1;j<=len;j++){
            if ( (i-j < 0 || i+j+1 >= len) || (s[i-j] != s[i+j+1])){
                string tmp;
                for (int k=i-j+1;k<=i+j;k++) tmp += s[k];
                for (int k=0;k<=(int)tmp.size()/2;k++) st.insert(sub(tmp,k,tmp.size()-k-1));
                break;
            }
        }
    }
    if (st.count("")) st.erase("");
    return st.size();
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    //work("00");
    //return 0;

    cin>>n>>arr; arr = '!' + arr;
    for (int i=1;i<=n;i++) res[i] = arr[i], boss[i] = i, sz[i] = 1;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        join(find(a), find(b));
        string s = res[find(a)];
        //out(s);
        cout<<work(s)<<endl;
    }

}

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