Submission #643514

#TimeUsernameProblemLanguageResultExecution timeMemory
643514mychecksedadPalindromi (COCI22_palindromi)C++17
10 / 110
1091 ms81876 KiB
/* 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; ll e[N], re[N], h[N], rh[N]; ll po(ll a, ll b){ll res = 1; while(b){if(b&1) (res*=a)%=MOD; b>>=1; (a*=a)%=MOD;} return res;} 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<int> ss, ss1; h[0] = 0, rh[s[x] + 1] = 0; for(int i = 1; i <= s[x]; ++i) h[i] = (h[i - 1] + e[i] * (str[x][i-1]-'0'+1)) % MOD; for(int i = s[x]; i >= 1; --i) rh[i] = (rh[i + 1] + e[s[x] - i + 1] * (str[x][i-1]-'0'+1)) % MOD; for(int i = 1; i <= str[x].size(); ++i){ // cout << str[x][i - 1]; for(int j = i; j <= str[x].size(); ++j){ int m = (i + j) >> 1; bool ok = 1; int has; if((i - j) & 1){ ok = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD) == ((rh[m + 1] - rh[j + 1] + MOD) * re[s[x] - j] % MOD); has = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD); }else{ ok = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD) == ((rh[m] - rh[j + 1] + MOD) * re[s[x] - j] % MOD); has = ((h[m] - h[i - 1] + MOD) * re[i - 1] % MOD); } if(ok) if((i-j)%2) ss.insert(has); else ss1.insert(has); } } return ans[x] = ss.size() + ss1.size(); } return -1; } }; int n; string s; void solve(){ cin >> n >> s; e[0] = re[0] = 1; for(int i = 1; i < N; ++i) e[i] = (e[i - 1] * 3) % MOD; re[N - 1] = po(e[N - 1], MOD - 2); for(int i = N - 2; i >= 0; --i) re[i] = (re[i + 1] * 3) % MOD; 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 (stderr)

Main.cpp: In member function 'll Dsu::merge(int, int)':
Main.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int i = 1; i <= str[x].size(); ++i){
      |                            ~~^~~~~~~~~~~~~~~~
Main.cpp:55:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                 for(int j = i; j <= str[x].size(); ++j){
      |                                ~~^~~~~~~~~~~~~~~~
Main.cpp:70:23: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   70 |                     if(ok) if((i-j)%2) ss.insert(has); else ss1.insert(has);
      |                       ^
Main.cpp: In function 'int main()':
Main.cpp:108:16: warning: unused variable 'aa' [-Wunused-variable]
  108 |     int T = 1, aa;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...