Submission #937475

#TimeUsernameProblemLanguageResultExecution timeMemory
937475gaga999Palindromi (COCI22_palindromi)C++17
110 / 110
218 ms175572 KiB
#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> // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } inline char gc() { const static int SZ = 1 << 16; static char buf[SZ], *p1, *p2; if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2)) return -1; return *p1++; } void rd() {} template <typename T, typename... U> void rd(T &x, U &...y) { x = 0; bool f = 0; char c = gc(); while (!isdigit(c)) f ^= !(c ^ 45), c = gc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); f && (x = -x), rd(y...); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } const int N = 1e5 + 5; struct TR { vector<int> len, kp, bk[2], to[2]; deque<int> dq; int cnt, ln, rn, sz; inline TR() : cnt(2), sz(0) { len = {-1, 0}, ln = rn = 1; // 0 kp = bk[0] = bk[1] = to[0] = to[1] = {0, 0}; } inline void add(int u, int vl) { len.pb(len[u] + 2); to[0].pb(0), to[1].pb(0); kp.pb(u ? to[vl][bk[vl][u]] : 1); to[vl][u] = cnt++; } void addr(int vl) { dq.pb(vl); int u; if (len[rn] < sz && dq[sz - len[rn] - 1] == vl) u = rn; else u = bk[vl][rn]; if (!to[vl][u]) { add(u, vl); int tp = dq[sz - len[kp.back()]]; bk[tp].pb(kp.back()); bk[tp ^ 1].pb(bk[tp ^ 1][kp.back()]); } rn = to[vl][u]; if (len[rn] == ++sz) ln = rn; } void addl(int vl) { int u; if (len[ln] < sz && dq[len[ln]] == vl) u = ln; else u = bk[vl][ln]; dq.push_front(vl); if (!to[vl][u]) { add(u, vl); int tp = dq[len[kp.back()]]; bk[tp].pb(kp.back()); bk[tp ^ 1].pb(bk[tp ^ 1][kp.back()]); } ln = to[vl][u]; if (len[ln] == ++sz) rn = ln; } } tr[N]; char s[N]; int ds[N]; int f(int x) { return ds[x] == x ? x : ds[x] = f(ds[x]); } signed main() { int n, x, y; scanf("%d%s", &n, s + 1); iota(ds + 1, ds + n + 1, 1); for (int i = 1; i <= n; i++) tr[i].addl(s[i] - '0'); for (int i = 1; i < n; i++) { scanf("%d%d", &x, &y); x = f(x), y = f(y); if (tr[x].sz > tr[y].sz) { for (int p = 0; p < tr[y].sz; p++) tr[x].addr(tr[y].dq[p]); printf("%d\n", tr[ds[y] = x].cnt - 2); } else { for (int p = tr[x].sz - 1; p >= 0; p--) tr[y].addl(tr[x].dq[p]); printf("%d\n", tr[ds[x] = y].cnt - 2); } } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:182:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |     scanf("%d%s", &n, s + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...