Submission #659128

#TimeUsernameProblemLanguageResultExecution timeMemory
659128shmadLampice (COCI19_lampice)C++17
42 / 110
5062 ms28488 KiB
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") #include <bits/stdc++.h> //#define int long long #define vt vector #define pb push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define ff first #define ss second #define dbg(x) cerr << #x << " = " << x << '\n' #define bit(x, i) ((x) >> (i) & 1) using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using vvt = vt< vt<ll> >; const int N = 1e6 + 5, mod = 1e9 + 7, B = 500; const ll inf = 1e18 + 7, LIM = (1ll << 60); const ld eps = 1e-6; int n, ans; string s; vt<int> g[N]; vt<char> c; int get () { int res = 0; for (int i = 0; i < sz(c); i++) { int l = i - 1, r = i + 1; while (l >= 0 && r < sz(c)) { if (c[l] == c[r]) l--, r++; else break; } l++, r--; res = max(res, r - l + 1); l = i - 1, r = i; while (l >= 0 && r < sz(c)) { if (c[l] == c[r]) l--, r++; else break; } l++, r--; res = max(res, r - l + 1); } return res; } void dfs (int v, int p = -1) { c.pb(s[v]); bool ok = 0; for (auto to: g[v]) { if (to != p) { ok = 1; dfs(to, v); } } if (!ok) ans = max(ans, get()); c.pop_back(); } bool pal (vt<char> &c) { vt<char> nc = c; reverse(all(nc)); return (c == nc); } void df (int v, int p = -1) { c.pb(s[v]); if (pal(c)) ans = max(ans, sz(c)); for (auto to: g[v]) { if (to != p) df(to, v); } c.pop_back(); } void solve () { cin >> n >> s; s = ' ' + s; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } if (n <= 100) { for (int i = 1; i <= n; i++) c.clear(), df(i); cout << ans; return; } for (int i = 1; i <= n; i++) { if (sz(g[i]) == 1) c.clear(), dfs(i); } cout << ans; cout << '\n'; } bool testcases = 0; signed main() { #ifdef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif cin.tie(0) -> sync_with_stdio(0); int test = 1; if (testcases) cin >> test; for (int cs = 1; cs <= test; cs++) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...