Submission #1156596

#TimeUsernameProblemLanguageResultExecution timeMemory
1156596beaconmcTeam Coding (EGOI24_teamcoding)C++20
100 / 100
1951 ms42336 KiB
#include <bits/stdc++.h> typedef int ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) using namespace std; vector<basic_string<ll>> edges; vector<ll> pref; ll n,k; ll timer = 0; ll tin[100005]; ll tout[100005]; ll depth[100005]; unordered_map<ll, ll> stuff[100005]; vector<ll> depths[100005]; vector<ll> consider; vector<ll> prefs[100005]; ll ans = -1, ans2 = 0; void dfs(ll a, ll d){ depths[d].push_back(a); depth[a] = d; stuff[d][pref[a]] += 1; tin[a] = timer; timer += 1; for (auto&i : edges[a]){ dfs(i, d+1); } tout[a] = timer; } ll numchild(ll a, ll k){ if (!(0<=k && k<100005)) return 0; vector<ll> &sus = depths[k]; if (sus.size()==0) return 0; if (depth[a] == k) return 0; ll lo = 0; ll hi = sus.size()-1; while (lo<hi){ ll mid = (lo+hi)/2; if (tin[sus[mid]] >= tin[a]) hi = mid; else lo = mid+1; } ll leftp = lo; lo = 0; hi = sus.size()-1; while (lo<hi){ ll mid = (lo+hi+1)/2; if (tout[sus[mid]] <= tout[a]) lo = mid; else hi = mid-1; } ll rightp = lo; if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0; return max((ll)0,rightp-leftp+1); } ll numspecialchild(ll a, ll k, ll c){ if (!(0<=k && k<100005)) return 0; vector<ll> &sus = depths[k]; if (sus.size()==0) return 0; if (depth[a] == k) return 0; ll lo = 0; ll hi = sus.size()-1; while (lo<hi){ ll mid = (lo+hi)/2; if (tin[sus[mid]] >= tin[a]) hi = mid; else lo = mid+1; } ll leftp = lo; lo = 0; hi = sus.size()-1; while (lo<hi){ ll mid = (lo+hi+1)/2; if (tout[sus[mid]] <= tout[a]) lo = mid; else hi = mid-1; } ll rightp = lo; ll ans = 0; if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0; FOR(i,leftp, rightp+1){ ans += (pref[sus[i]]==c); } return ans; } void solve(ll a){ ll tans = 1; ll tans2 = 0; for (auto&i : consider){ ll temp = numchild(a,i); if (temp==0) continue; tans += min(temp, stuff[i][pref[a]]); tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]); } if (tans > ans) ans = tans, ans2 = tans2; else if (tans == ans) ans2 = min(ans2, tans2); } void solve2(ll a){ ll tans = 1; ll tans2 = 0; FOR(i, depth[a]+1, n){ ll temp = numchild(a,i); if (temp==0) break; tans += min(temp, stuff[i][pref[a]]); tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]); } if (tans > ans) ans = tans, ans2 = tans2; else if (tans == ans) ans2 = min(ans2, tans2); } void dfs2(ll a, ll p){ if(pref[a] == p){ solve2(a); return; } for (auto& i :edges[a]) dfs2(i,p); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; FOR(i,0,n) edges.push_back({}), pref.push_back(0); FOR(i,0,n){ cin >> pref[i]; prefs[pref[i]].push_back(i); } FOR(i,1,n){ ll temp; cin >> temp; edges[temp].push_back(i); } dfs(0,0); FOR(p,0,k){ if (prefs[p].size() > 400) dfs2(0,p); else{ consider.clear(); unordered_set<ll> temps; for (auto&i : prefs[p]) temps.insert(depth[i]); for (auto&i : temps)consider.push_back(i); for (auto&i : prefs[p]){ solve(i); } } } cout << ans << " " << ans2 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...