oj.uz

Submission #643504

# Submission time Handle Problem Language Result Execution time Memory
643504 2022-09-22T08:14:59 Z mychecksedad Palindromi (COCI22_palindromi) C++17
10 / 110
 1000 ms 66516 KB 
/* 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 7 ms 412 KB Output is correct
3 Correct 5 ms 320 KB Output is correct
4 Correct 10 ms 316 KB Output is correct
5 Correct 13 ms 412 KB Output is correct
6 Correct 23 ms 396 KB Output is correct
7 Correct 20 ms 396 KB Output is correct
8 Correct 21 ms 340 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 25 ms 392 KB Output is correct
11 Correct 18 ms 396 KB Output is correct
12 Correct 2 ms 316 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 0 ms 324 KB Output is correct
2 Correct 7 ms 412 KB Output is correct
3 Correct 5 ms 320 KB Output is correct
4 Correct 10 ms 316 KB Output is correct
5 Correct 13 ms 412 KB Output is correct
6 Correct 23 ms 396 KB Output is correct
7 Correct 20 ms 396 KB Output is correct
8 Correct 21 ms 340 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 25 ms 392 KB Output is correct
11 Correct 18 ms 396 KB Output is correct
12 Correct 2 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Execution timed out 1088 ms 1124 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 66516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 7 ms 412 KB Output is correct
3 Correct 5 ms 320 KB Output is correct
4 Correct 10 ms 316 KB Output is correct
5 Correct 13 ms 412 KB Output is correct
6 Correct 23 ms 396 KB Output is correct
7 Correct 20 ms 396 KB Output is correct
8 Correct 21 ms 340 KB Output is correct
9 Correct 22 ms 340 KB Output is correct
10 Correct 25 ms 392 KB Output is correct
11 Correct 18 ms 396 KB Output is correct
12 Correct 2 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Execution timed out 1088 ms 1124 KB Time limit exceeded
16 Halted 0 ms 0 KB -