oj.uz

Submission #705013

# Submission time Handle Problem Language Result Execution time Memory
705013 2023-03-03T08:00:35 Z Cookie197 Palindromi (COCI22_palindromi) C++17
10 / 110
 1000 ms 848 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 368 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 37 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 35 ms 368 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 32 ms 376 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 368 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 37 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 35 ms 368 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 32 ms 376 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Execution timed out 1069 ms 548 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 368 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 37 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 35 ms 368 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 32 ms 376 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Execution timed out 1069 ms 548 KB Time limit exceeded
16 Halted 0 ms 0 KB -