Submission #885786

#TimeUsernameProblemLanguageResultExecution timeMemory
885786AgentPenginLampice (COCI19_lampice)C++14
110 / 110
1878 ms29276 KiB
/** * author: AgentPengin ( Độc cô cầu bại ) * created: 23.12.2022 10:08:02 * too lazy to update time **/ #include<bits/stdc++.h> #define EL '\n' #define fi first #define se second #define NAME "TASK" #define ll long long #define lcm(a,b) (a/gcd(a,b))*b #define db(val) "["#val" = " << (val) << "] " #define bend(v) (v).begin(),(v).end() #define sz(v) (int)(v).size() #define ex exit(0) using namespace std; const ll mod = 1e9 + 7; const int inf = 0x1FFFFFFF; const int MAXN = 2e5 + 5; const ll base = 35711; int n,Len,valid[MAXN],child[MAXN],mx_depth; char a[MAXN]; vector<int> adj[MAXN]; vector<pair<int,ll>> b; ll po[MAXN]; unordered_map<ll,bool> f[MAXN]; void countChild(int u,int p) { child[u] = 1; for (auto v : adj[u]) { if (v != p && valid[v]) { countChild(v,u); child[u] += child[v]; } } } bool dfs(int u,int p,int h,ll hashdown,ll hashup) { if (h > Len) return false; if (p) { hashdown = (hashdown * base + a[u]) % mod; } hashup = (hashup + 1LL * a[u] * po[h - 1]) % mod; ll x = (hashup * po[Len - h] - hashdown + mod) % mod; if (!p) f[h][x] = true; if (f[Len - h + 1].find(x) != f[Len - h + 1].end()) return true; for (auto v : adj[u]) { if (v != p && valid[v]) { if (!p) b.clear(); if (dfs(v,u,h + 1,hashdown,hashup)) return true; if (!p) { for (auto x : b) { f[x.fi][x.se] = true; } } } } mx_depth = max(mx_depth,h); b.push_back({h,x}); return false; } bool solve(int u,int n) { countChild(u,0); int flag = 1,half = n / 2; while(flag) { flag = 0; for (auto v : adj[u]) { if (valid[v] && child[v] < child[u] && child[v] > half) { u = v; flag = true; break; } } } countChild(u,0); if (dfs(u,0,1,0,0)) return true; for (int i = 1;i <= mx_depth;i++) f[i].clear(); mx_depth = 0; valid[u] = false; for (auto v : adj[u]) { if (valid[v]) { if (solve(v,child[v])) return true; } } return false; } bool check(int len) { Len = len; for (int i = 1;i <= n;i++) { valid[i] = 1; f[i].clear(); } return solve(1,n); } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if (ifstream(NAME".inp")) { freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout); } cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; for (int i = 1;i < n;i++) { int u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } po[0] = 1; for (int i = 1;i <= n;i++) po[i] = po[i - 1] * base % mod; int l = 0,r = (n - 1) / 2; while(l < r) { int mid = (l + r + 1) >> 1; if (check(mid * 2 + 1)) { l = mid; } else { r = mid - 1; } } int ans = r * 2 + 1; l = 0,r = n / 2; while(l < r) { int mid = (l + r + 1) >> 1; if (check(mid * 2)) { l = mid; } else r = mid - 1; } cout << max(ans,r * 2); cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; } // agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(NAME".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...