Submission #635687

#	Time	Username	Problem	Language	Result	Execution time	Memory
635687		ghostwriter	Palindromi (COCI22_palindromi)	C++14	30 / 110	44 ms	10656 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const pi M = {1e9 + 7, 1e9 + 9};
const pi base = {37, 127};
const int N = 1e5 + 5;
int n;
pi P[N];
str s;
pi q[N];
namespace subtask12 {
	int p[N];
	str a1[N];
	set<pi> a2[N];
	int getp(int i) { return i == p[i]? i : p[i] = getp(p[i]); }
	int join(int x, int y) {
		x = getp(x);
		y = getp(y);
		if (sz(a2[x]) < sz(a2[y])) swap(a2[x], a2[y]);
		EACH(i, a2[y]) a2[x].insert(i);
		int m1 = sz(a1[x]);
		int m2 = sz(a1[y]);
		vpi h(m1 + m2 + 2), h1(m1 + m2 + 2);
		a1[x] += a1[y];
		auto get = [&](int l, int r) -> pi {
			pi rs;
			rs.st = (h[r].st - 1LL * (l == 0? 0 : h[l - 1].st) * P[r - l + 1].st % M.st + M.st) % M.st;
			rs.nd = (h[r].nd - 1LL * (l == 0? 0 : h[l - 1].nd) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
			return rs;
		};
		auto get1 = [&](int l, int r) -> pi {
			pi rs;
			rs.st = (h1[l].st - 1LL * h1[r + 1].st * P[r - l + 1].st % M.st + M.st) % M.st;
			rs.nd = (h1[l].nd - 1LL * h1[r + 1].nd * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
			return rs;
		};
		pi cur = {0, 0};
		FOR(i, 0, m1 + m2 - 1) {
			cur.st = (1LL * cur.st * base.st % M.st + a1[x][i] - '0' + 1) % M.st;
			cur.nd = (1LL * cur.nd * base.nd % M.nd + a1[x][i] - '0' + 1) % M.nd;
			h[i] = cur;
		}
		cur = {0, 0};
		FOS(i, m1 + m2 - 1, 0) {
			cur.st = (1LL * cur.st * base.st % M.st + a1[x][i] - '0' + 1) % M.st;
			cur.nd = (1LL * cur.nd * base.nd % M.nd + a1[x][i] - '0' + 1) % M.nd;
			h1[i] = cur;
		}
		FOR(i, 0, m1 - 1)
		FOR(j, m1, m1 + m2 - 1) {
			pi tmp = get(i, j);
			if (tmp == get1(i, j)) a2[x].insert(tmp);
		}
		p[y] = x;
		return sz(a2[x]);
	}
	void solve() {
		FOR(i, 1, n) {
			p[i] = i;
			a1[i].pb(s[i]);
			a2[i].insert({s[i] - '0' + 1, s[i] - '0' + 1});
		}
		FOR(i, 1, n - 1) {
			int a = q[i].st, b = q[i].nd;
			cout << join(a, b) << '\n';
		}
	}
}
namespace subtask3 {
	pi h[N];
	int sa[N];
	void solve() {
	}
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> s;
    P[0] = {1, 1};
    FOR(i, 1, n) {
    	P[i].st = 1LL * P[i - 1].st * base.st % M.st;
    	P[i].nd = 1LL * P[i - 1].nd * base.nd % M.nd;
    }
    s = "#" + s + "#";
    FOR(i, 1, n - 1) cin >> q[i].st >> q[i].nd;
    if (n <= 1000) {
    	subtask12::solve();
    	return 0;
    }
    subtask3::solve();
    return 0;
}
/*
3
010
1 2
2 3
*/

Compilation message (stderr)

Main.cpp: In function 'int subtask12::join(int, int)':
Main.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
Main.cpp:52:3: note: in expansion of macro 'EACH'
   52 |   EACH(i, a2[y]) a2[x].insert(i);
      |   ^~~~
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:70:3: note: in expansion of macro 'FOR'
   70 |   FOR(i, 0, m1 + m2 - 1) {
      |   ^~~
Main.cpp:25:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   25 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
Main.cpp:76:3: note: in expansion of macro 'FOS'
   76 |   FOS(i, m1 + m2 - 1, 0) {
      |   ^~~
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:81:3: note: in expansion of macro 'FOR'
   81 |   FOR(i, 0, m1 - 1)
      |   ^~~
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:82:3: note: in expansion of macro 'FOR'
   82 |   FOR(j, m1, m1 + m2 - 1) {
      |   ^~~
Main.cpp: In function 'void subtask12::solve()':
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:90:3: note: in expansion of macro 'FOR'
   90 |   FOR(i, 1, n) {
      |   ^~~
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:95:3: note: in expansion of macro 'FOR'
   95 |   FOR(i, 1, n - 1) {
      |   ^~~
Main.cpp: In function 'int main()':
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:113:5: note: in expansion of macro 'FOR'
  113 |     FOR(i, 1, n) {
      |     ^~~
Main.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
Main.cpp:118:5: note: in expansion of macro 'FOR'
  118 |     FOR(i, 1, n - 1) cin >> q[i].st >> q[i].nd;
      |     ^~~

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