Submission #499009

#TimeUsernameProblemLanguageResultExecution timeMemory
499009hoanghq2004Lampice (COCI19_lampice)C++14
110 / 110
4168 ms12108 KiB
#include <bits/stdc++.h> #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") using namespace std; const int N = 5e4 + 10; const int mod = 1e9 + 7; const int base = 29; int n, ti; char c[N]; int big[N], sz[N], del[N]; vector <int> g[N]; void dfs(int u, int p) { big[u] = 0, sz[u] = 1; for (auto v: g[u]) { if (v == p || del[v] == ti) continue; dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[big[u]]) big[u] = v; } } int centroid(int u) { int num = sz[u] / 2; while (sz[big[u]] > num) u = big[u]; return u; } int H[N], power[N]; int rH[N]; int get_hash(int L, int R) { return (0LL + H[R] - 1LL * H[L - 1] * power[R - L + 1] + 1LL * mod * mod) % mod; } int check(int u, int len) { dfs(u, 0); u = centroid(u); del[u] = ti; H[1] = c[u] - 'a' + 1; unordered_set <int> s; function <void(int, int, int)> add = [&](int u, int p, int d) { if (d * 2 > len + 3) return; H[d] = (1LL * H[d - 1] * base + c[u] - 'a' + 1) % mod; s.insert(H[d]); for (auto v: g[u]) { if (v == p || del[v] == ti) continue; add(v, u, d + 1); } }; rH[1] = c[u] - 'a' + 1; s.insert(H[1]); int ok = 0; function <void(int, int, int)> calc = [&](int u, int p, int d) { if (d > len || ok) return; H[d] = (1LL * H[d - 1] * base + c[u] - 'a' + 1) % mod; int rem = len - d + 1; rH[d] = (1LL * power[d - 1] * (c[u] - 'a' + 1) + rH[d - 1]) % mod; if (d * 2 - len > 0 && rH[d * 2 - len] == H[d * 2 - len]) { if (s.find(get_hash(d * 2 - len, d)) != s.end()) { ok = 1; return; } } for (auto v: g[u]) { if (v == p || del[v] == ti) continue; calc(v, u, d + 1); } }; for (auto v: g[u]) { if (del[v] == ti) continue; calc(v, u, 2); if (ok) return 1; add(v, u, 2); } s.clear(); reverse(g[u].begin(), g[u].end()); for (auto v: g[u]) { if (del[v] == ti) continue; calc(v, u, 2); if (ok) return 1; add(v, u, 2); } for (auto v: g[u]) { if (del[v] == ti) continue; if (check(v, len)) return 1; } return 0; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> c[i]; power[0] = 1; for (int i = 1; i <= n; ++i) power[i] = 1LL * power[i - 1] * base % mod; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } int ans = 0; int L = 0, R = n / 2; while (R - L > 1) { int mid = L + R >> 1; ++ti; if (check(1, mid * 2)) L = mid; else R = mid; } ++ti; if (check(1, R * 2)) ans = R * 2; else ans = L * 2; if (!ans) ans = 1; L = 1, R = n / 2 + 1; while (R - L > 1) { int mid = L + R >> 1; ++ti; if (check(1, mid * 2 - 1)) L = mid; else R = mid; } ++ti; if (check(1, R * 2 - 1)) ans = max(ans, R * 2 - 1); else ans = max(ans, L * 2 - 1); cout << ans; }

Compilation message (stderr)

lampice.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
lampice.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
lampice.cpp: In lambda function:
lampice.cpp:61:13: warning: unused variable 'rem' [-Wunused-variable]
   61 |         int rem = len - d + 1;
      |             ^~~
lampice.cpp: In function 'int main()':
lampice.cpp:110:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = L + R >> 1;
      |                   ~~^~~
lampice.cpp:121:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mid = L + R >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...