?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
239873943 |
Practice: ghoshsai5000 |
1916E - 48 | C++17 (GCC 7-32) | Accepted | 732 ms | 71796 KB | 2024-01-01 14:09:59 | 2024-01-01 14:09:59 |
#include <iostream> #include <vector> using namespace std; const int MAX_N = 3e5 + 5; int no_of_vertices; vector <vector <int> > tree(MAX_N); long long max_tree[7*MAX_N], lazy[7*MAX_N],answer; int A[MAX_N],time_in[MAX_N], time_out[MAX_N]; vector <int> occurences[MAX_N]; #define LEFT(n) (2*n) #define RIGHT(n) (2*n + 1) void initialize() { for(int i = 1; i <= no_of_vertices; i++) { occurences[i].clear(); tree[i].clear(); } } void propagate(int n, int left, int right) { if(left != right) { lazy[LEFT(n)] += lazy[n]; lazy[RIGHT(n)] += lazy[n]; } max_tree[n] += lazy[n]; lazy[n] = 0; } void build(int n, int left, int right) { lazy[n] = 0; if(left == right) { max_tree[n] = 0; return; } int mid = (left + right)/2; build(LEFT(n), left, mid); build(RIGHT(n), mid + 1, right); max_tree[n] = max(max_tree[LEFT(n)], max_tree[RIGHT(n)]); } void update(int n, int left, int right, int query_left, int query_right, int value) { if(lazy[n] != 0) { propagate(n, left, right); } if(right < query_left || query_right < left) { return; } //Do Range Updates, not Point Updates - That was the reason for TLE if(query_left <= left && right <= query_right) { lazy[n] += value; propagate(n, left, right); return; } int mid = (left + right)/2; update(LEFT(n), left, mid, query_left, query_right, value); update(RIGHT(n), mid + 1, right,query_left, query_right, value); max_tree[n] = max(max_tree[LEFT(n)], max_tree[RIGHT(n)]); } long long get_sum(int n, int left, int right, int query_left, int query_right) { if(lazy[n] != 0) { propagate(n, left, right); } if(right < query_left || query_right < left || query_right < query_left) { return 0; } if(query_left <= left && right <= query_right) { return max_tree[n]; } int mid = (left + right)/2; long long left_answer = get_sum(LEFT(n), left, mid, query_left, query_right); long long right_answer = get_sum(RIGHT(n), mid + 1, right, query_left, query_right); long long answer = max(left_answer, right_answer); return answer; } void remove_occurence(int v) { update(1, 1, 2*no_of_vertices, time_in[v], time_out[v], -1); } void add_occurence(int v) { update(1, 1, 2*no_of_vertices, time_in[v], time_out[v], 1); } long long get_distinct_count(int v) { return get_sum(1, 1, 2*no_of_vertices, time_in[v], time_out[v]); } int in_subtree(int u, int v) { return (time_in[v] <= time_in[u] && time_out[u] <= time_out[v]); } void dfs_time(int v, int time) { time_in[v] = time++; for(int child_v : tree[v]) { dfs_time(child_v, time); time = time_out[child_v] + 1; } time_out[v] = time; } void dfs(int v) { for(int child_v : tree[v]) { dfs(child_v); } int value = A[v]; while(occurences[value].size() > 0 && in_subtree(occurences[value].back(), v)) { int u = occurences[value].back(); remove_occurence(u); occurences[value].pop_back(); } add_occurence(v); occurences[value].push_back(v); long long max_1 = 1, max_2 = 1; for(int child_v : tree[v]) { long long max_distinct_in_this_child_subtree = get_distinct_count(child_v); if(max_distinct_in_this_child_subtree >= max_1) { max_2 = max_1; max_1 = max_distinct_in_this_child_subtree; } else if(max_distinct_in_this_child_subtree > max_2) { max_2 = max_distinct_in_this_child_subtree; } } answer = max(answer, max_1*max_2); } void solve() { cin >> no_of_vertices; answer = 1; initialize(); build(1, 1, 2*no_of_vertices); int parent; for(int v = 2; v <= no_of_vertices; v++) { cin >> parent; tree[parent].push_back(v); } for(int i = 1; i <= no_of_vertices; i++) { cin >> A[i]; } time_in[0] = time_out[0] = 0; dfs_time(1, 1); dfs(1); cout << answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int no_of_test_cases; cin >> no_of_test_cases; while(no_of_test_cases--) solve(); return 0; }
?
?
?
?