oj.uz

Submission #937423

# Submission time Handle Problem Language Result Execution time Memory
937423 2024-03-04T03:39:20 Z gaga999 Palindromi (COCI22_palindromi) C++17
110 / 110
 324 ms 145544 KB 
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <sstream>
#include <assert.h>
#include <climits>
#include <sstream>
#include <numeric>
#include <time.h>
#include <limits.h>
#include <list>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <complex>
#include <chrono>
#include <fstream>
#include <functional>
#include <unistd.h>

using namespace std;

typedef long long llint;
typedef pair<int, int> pi;

const int MAXN = 100005;

int n;
string s;
int p[MAXN];

struct olbat
{
    int cnt, siz, lef, rig;
    vector<int> len, link, suf[2], child[2];
    deque<char> dq;

    olbat()
    {
        cnt = 2;
        siz = 0;
        lef = rig = 1;
        len = {-1, 0};
        child[0] = child[1] = {0, 0};
        link = suf[0] = suf[1] = {0, 0};
    }

    void add_new_node(int par, char c)
    {
        len.push_back(len[par] + 2);

        child[c - '0'][par] = cnt;
        child[0].push_back(0);
        child[1].push_back(0);

        if (par != 0)
        {
            link.push_back(child[c - '0'][suf[c - '0'][par]]);
        }
        else
        {
            link.push_back(1);
        }
        suf[0].push_back(0);
        suf[1].push_back(0);

        cnt++;
    }

    void add_rig(char c)
    {
        dq.push_back(c);

        int par;
        if (len[rig] < siz && dq[siz - len[rig] - 1] == c)
        {
            par = rig;
        }
        else
        {
            par = suf[c - '0'][rig];
        }

        if (child[c - '0'][par] == 0)
        {
            add_new_node(par, c);
            if (dq[siz - len[link[cnt - 1]]] == '0')
            {
                suf[0][cnt - 1] = link[cnt - 1];
                suf[1][cnt - 1] = suf[1][link[cnt - 1]];
            }
            else
            {
                suf[0][cnt - 1] = suf[0][link[cnt - 1]];
                suf[1][cnt - 1] = link[cnt - 1];
            }
        }

        siz++;

        rig = child[c - '0'][par];
        if (len[rig] == siz)
            lef = rig;
    }

    void add_lef(char c)
    {
        int par;
        if (len[lef] < siz && dq[len[lef]] == c)
        {
            par = lef;
        }
        else
        {
            par = suf[c - '0'][lef];
        }

        if (child[c - '0'][par] == 0)
        {
            add_new_node(par, c);
            if (len[link[cnt - 1]] - 1 >= 0 && dq[len[link[cnt - 1]] - 1] == '0' || len[link[cnt - 1]] - 1 < 0 && c == '0')
            {
                suf[0][cnt - 1] = link[cnt - 1];
                suf[1][cnt - 1] = suf[1][link[cnt - 1]];
            }
            else
            {
                suf[0][cnt - 1] = suf[0][link[cnt - 1]];
                suf[1][cnt - 1] = link[cnt - 1];
            }
        }

        dq.push_front(c);
        siz++;

        lef = child[c - '0'][par];
        if (len[lef] == siz)
            rig = lef;
    }

    // void dfs (int node, string s) {
    //     cout << node << ": " << s << endl;
    //     string novi;
    //     if (node == 0) novi = "0"; else novi = "0" + s + "0";
    //     if (child[0][node]) dfs(child[0][node], novi);
    //     if (node == 0) novi = "1"; else novi = "1" + s + "1";
    //     if (child[1][node]) dfs(child[1][node], novi);
    // }

    void ispis()
    {
        for (auto c : dq)
            cout << c;
        cout << endl;
    }

    // void popis()
    // {
    //     dfs(0, "");
    //     dfs(1, "");
    // }
} ol[MAXN];

int nadi(int a)
{
    if (a == p[a])
        return a;
    return p[a] = nadi(p[a]);
}

int spoji(int a, int b)
{
    a = nadi(a);
    b = nadi(b);
    if (ol[a].siz > ol[b].siz)
    {
        for (int i = 0; i < ol[b].dq.size(); i++)
        {
            ol[a].add_rig(ol[b].dq[i]);
        }
        p[b] = a;
    }
    else
    {
        for (int i = (int)ol[a].dq.size() - 1; i >= 0; i--)
        {
            ol[b].add_lef(ol[a].dq[i]);
        }
        p[a] = b;
    }
    return p[a];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        ol[i].add_rig(s[i - 1]);
        p[i] = i;
    }
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        int node = spoji(a, b);
        cout << ol[node].cnt - 2 << endl;
    }
    /*cin >> n;
    for (int i = 1; i <= n; i++) {
        char c, d;
        cin >> c >> d;
        if (d == 'L') ol[0].add_lef(c); else ol[0].add_rig(c);
    }
    cout << ol[0].cnt - 2;*/
    return 0;
}

Compilation message

Main.cpp: In member function 'void olbat::add_lef(char)':
Main.cpp:136:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  136 |             if (len[link[cnt - 1]] - 1 >= 0 && dq[len[link[cnt - 1]] - 1] == '0' || len[link[cnt - 1]] - 1 < 0 && c == '0')
Main.cpp: In function 'int spoji(int, int)':
Main.cpp:192:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |         for (int i = 0; i < ol[b].dq.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 101968 KB Output is correct
2 Correct 85 ms 102156 KB Output is correct
3 Correct 90 ms 102232 KB Output is correct
4 Correct 84 ms 102156 KB Output is correct
5 Correct 85 ms 102164 KB Output is correct
6 Correct 63 ms 102080 KB Output is correct
7 Correct 64 ms 101972 KB Output is correct
8 Correct 64 ms 101972 KB Output is correct
9 Correct 63 ms 102028 KB Output is correct
10 Correct 89 ms 101976 KB Output is correct
11 Correct 64 ms 101972 KB Output is correct
12 Correct 83 ms 102228 KB Output is correct
13 Correct 63 ms 102228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 101968 KB Output is correct
2 Correct 85 ms 102156 KB Output is correct
3 Correct 90 ms 102232 KB Output is correct
4 Correct 84 ms 102156 KB Output is correct
5 Correct 85 ms 102164 KB Output is correct
6 Correct 63 ms 102080 KB Output is correct
7 Correct 64 ms 101972 KB Output is correct
8 Correct 64 ms 101972 KB Output is correct
9 Correct 63 ms 102028 KB Output is correct
10 Correct 89 ms 101976 KB Output is correct
11 Correct 64 ms 101972 KB Output is correct
12 Correct 83 ms 102228 KB Output is correct
13 Correct 63 ms 102228 KB Output is correct
14 Correct 64 ms 101972 KB Output is correct
15 Correct 102 ms 102236 KB Output is correct
16 Correct 69 ms 102228 KB Output is correct
17 Correct 86 ms 102228 KB Output is correct
18 Correct 65 ms 102228 KB Output is correct
19 Correct 87 ms 102228 KB Output is correct
20 Correct 66 ms 102228 KB Output is correct
21 Correct 90 ms 102228 KB Output is correct
22 Correct 64 ms 102228 KB Output is correct
23 Correct 87 ms 102228 KB Output is correct
24 Correct 66 ms 102228 KB Output is correct
25 Correct 65 ms 102484 KB Output is correct
26 Correct 73 ms 102484 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 104080 KB Output is correct
2 Correct 231 ms 106544 KB Output is correct
3 Correct 237 ms 104276 KB Output is correct
4 Correct 227 ms 106684 KB Output is correct
5 Correct 238 ms 104156 KB Output is correct
6 Correct 226 ms 106764 KB Output is correct
7 Correct 242 ms 104276 KB Output is correct
8 Correct 222 ms 106476 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 101968 KB Output is correct
2 Correct 85 ms 102156 KB Output is correct
3 Correct 90 ms 102232 KB Output is correct
4 Correct 84 ms 102156 KB Output is correct
5 Correct 85 ms 102164 KB Output is correct
6 Correct 63 ms 102080 KB Output is correct
7 Correct 64 ms 101972 KB Output is correct
8 Correct 64 ms 101972 KB Output is correct
9 Correct 63 ms 102028 KB Output is correct
10 Correct 89 ms 101976 KB Output is correct
11 Correct 64 ms 101972 KB Output is correct
12 Correct 83 ms 102228 KB Output is correct
13 Correct 63 ms 102228 KB Output is correct
14 Correct 64 ms 101972 KB Output is correct
15 Correct 102 ms 102236 KB Output is correct
16 Correct 69 ms 102228 KB Output is correct
17 Correct 86 ms 102228 KB Output is correct
18 Correct 65 ms 102228 KB Output is correct
19 Correct 87 ms 102228 KB Output is correct
20 Correct 66 ms 102228 KB Output is correct
21 Correct 90 ms 102228 KB Output is correct
22 Correct 64 ms 102228 KB Output is correct
23 Correct 87 ms 102228 KB Output is correct
24 Correct 66 ms 102228 KB Output is correct
25 Correct 65 ms 102484 KB Output is correct
26 Correct 73 ms 102484 KB Output is correct
27 Correct 233 ms 104080 KB Output is correct
28 Correct 231 ms 106544 KB Output is correct
29 Correct 237 ms 104276 KB Output is correct
30 Correct 227 ms 106684 KB Output is correct
31 Correct 238 ms 104156 KB Output is correct
32 Correct 226 ms 106764 KB Output is correct
33 Correct 242 ms 104276 KB Output is correct
34 Correct 222 ms 106476 KB Output is correct
35 Correct 64 ms 101996 KB Output is correct
36 Correct 299 ms 124500 KB Output is correct
37 Correct 318 ms 120888 KB Output is correct
38 Correct 314 ms 125136 KB Output is correct
39 Correct 324 ms 122196 KB Output is correct
40 Correct 244 ms 106624 KB Output is correct
41 Correct 269 ms 104188 KB Output is correct
42 Correct 224 ms 106548 KB Output is correct
43 Correct 238 ms 104000 KB Output is correct
44 Correct 225 ms 106544 KB Output is correct
45 Correct 236 ms 104020 KB Output is correct
46 Correct 276 ms 145544 KB Output is correct
47 Correct 283 ms 131156 KB Output is correct