Submission #1140053

#TimeUsernameProblemLanguageResultExecution timeMemory
1140053btninhLampice (COCI19_lampice)C++20
25 / 110
1435 ms50052 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pii pair<int,int> #define INF 1e9 #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define FORD(i, a, b) for(int i = a; i >= b; --i) #define TASK "test" using namespace std; const int N = 50003; const int mod = 1e9 + 7; const int base = 311; int n, si[N], pw[N], mx = 0, curCen; bool vis[N]; char s[N]; vector<int> g[N]; vector<pii> st; map<int,bool> f[N]; int dfs(int u, int p){ si[u] = 1; for(auto v : g[u]){ if (v == p || vis[v]) continue; si[u] += dfs(v, u); } return si[u]; } int centroid(int u, int p, int n){ for(auto v : g[u]){ if (v != p && !vis[v] && si[v] > n / 2) return centroid(v, u, n); } return u; } bool ck(int u, int p, int dep, int up, int down, int k){ if (dep > k) return false; down = (down * base + s[u]) % mod; up = (s[u] * pw[dep - 1] + up) % mod; int val = (up * pw[k - dep] - down + mod) % mod; if (f[k - dep + 1].find(val) != f[k - dep + 1].end()) return true; st.pb({dep, val}); mx = max(mx, dep); for(auto v : g[u]){ if (v != p && !vis[v]) if(ck(v, u, dep + 1, up, down, k)) return true; } if (p == curCen){ for(auto x : st){ f[x.fi][x.se] = true; } } return false; } bool build(int u, int k){ u = centroid(u, 0, dfs(u, 0)); vis[u] = true; mx = 0; curCen = u; f[1][(-s[u] + mod) % mod] = true; for(auto v : g[u]){ if (vis[v]) continue; if (ck(v, u, 2, s[u], 0, k)) return true; } FOR(i, 0, mx) f[i].clear(); st.clear(); for(auto v : g[u]){ if (!vis[v]){ if (build(v, k)) return true; } } return false; } void Proc(){ cin >> n; FOR(i, 1, n) cin >> s[i]; FOR(i, 1, n - 1){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } pw[0] = 1; FOR(i, 1, n) pw[i] = pw[i - 1] * base % mod; int l = 1, r = n / 2, ans = 1; while (l <= r){ int mid = (l + r) >> 1; FOR(i, 1, n) vis[i] = false; if (build(1, 2 * mid + 1)){ ans = max(ans, 2 * mid + 1); l = mid + 1; } else r = mid - 1; } l = 1, r = n / 2; while (l <= r){ int mid = (l + r) >> 1; FOR(i, 1, n) vis[i] = false; if (build(1, 2 * mid)){ ans = max(ans, 2 * mid); l = mid + 1; } else r = mid - 1; } cout << ans; } signed main() { if(fopen("test.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ios::sync_with_stdio(false); cin.tie(nullptr); int T; T = 1; //cin >> T; while (T--) Proc(); }

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...