Problem link
Practice
Contest
Author: Pratik
Tester: Nitin gupta
Editorialist: Pratik
DIFFICULTY:
CAKEWALK, SIMPLE, EASY, MEDIUM or HARD.
Intermediate levels like SIMPLE-EASY, EASY-MEDIUM, MEDIUM-HARD are also possible.
PREREQUISITES:
Greedy, DP, Trees.
PROBLEM:
You are given a rooted tree having nodes N . Every node have value equal to zero initially ,
Let’s call it version 1. You will be given Q queries of two type:-
11 ver1ver1 ver2ver2 vv cc
You have to make version ver2ver2 from version ver1ver1 by adding value cc in subtree of vertex vv at alternate levels , starting from level of vertex vv.
22 ver1ver1 vv
You have to tell value of vertex vv in version ver1ver1
It is guaranteed that in query , version ver1ver1 already exist and version ver2ver2 does not exist .
EXPLANATION:
1
/ \
2 3
/
4
/
5
value in version 1 - > [0,0,0,0,0]
value in version 2 - > [0,0,0,1,0]
value in version 3 - > [2,0,0,3,0]
value in version 4 - > [0,4,0,1,4]
Setter's Solution
#pragma GCC optimization (“O3”)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ordered_set tree<ll,null_type,less, rb_tree_tag,tree_order_statistics_node_update>
#define endl “\n”
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll M = 1e9 + 7;
const ll mxx = 2e5 + 5;
vector adj[mxx];
vector G[mxx];
ll cnt;
ll parent_in_G[mxx], parent[mxx], level[mxx];
pair<ll, ll> info[mxx];
void dfs_for_parent(ll u, ll p)
{
parent_in_G[u] = p;
for(auto x : G[u])
if(x != p)dfs_for_parent(x, u);
}
void dfs_for_level(ll u, ll lev)
{
level[u] = lev;
for(auto x : adj[u])
dfs_for_level(x, lev + 1);
}
ll tin[mxx], tout[mxx], timer;
void dfs(ll u)
{
tin[u] = timer++;
for(auto x : adj[u])
dfs(x);
tout[u] = timer++;
}
ll solve(ll version, ll u)
{
ll res = 0;
while(version)
{
ll v = info[version].first;
ll c = info[version].second;
if(level[u] >= level[v] && tin[u] >= tin[v] && tin[u] <= tout[v])
{
if((level[u] - level[v]) % 2 == 0)res += c;
}
version = parent_in_G[version];
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
fast
ll n, q;
cin >> n;
for(ll i = 2; i <= n; i++)
{
ll k;
cin >> k;
parent[i] = k;
adj[k].push_back(i);
}
cin >> q;
map<ll, ll> m;
m[1] = 1;
vector<pair<ll, ll>> v;
cnt = 2;
for(ll i = 0; i < q; i++)
{
ll t;
cin >> t;
if(t == 1)
{
ll v1, v2, u, c;
cin >> v1 >> v2 >> u >> c;
v1 = m[v1];
v2 = cnt;
m[v2] = cnt++;
info[v2] = {u, c};
G[v1].push_back(v2);
}
else
{
ll u, ver;
cin >> u >> ver;
u = m[u];
v.push_back({u, ver});
}
}
for(ll i = 1; i < cnt; i++)parent_in_G[i] = -1;
for(ll i = 1; i < cnt; i++)
if(parent_in_G[i] == -1)dfs_for_parent(i, 0);
dfs_for_level(1, 0);
timer = 0;
dfs(1);
for(ll i = 0; i < v.size(); i++)
cout << solve(v[i].first, v[i].second) << endl;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define forx(v) for(int x=0; x<v; x++)
#define fory(v) for(int y=0; y<v; y++)
#define ll long long
#define ld long double
#define MAX (int)(4*pow(10,3)+ 10)
#define pb(a) push_back(a)
ll inf = pow(10,18);
ll modulo = pow(10,9) + 7;
double eps = 1e-6;
ifstream in;
ofstream out;
int tin[MAX];
int tout[MAX];
vector sums[MAX];
vector g[MAX];
int dep[MAX];
void dfs(int hd,int& tim){
tin[hd] = tim;
for(auto& hr : g[hd]){
++tim;
dep[hr] = dep[hd] + 1;
dfs(hr, tim);
}
tout[hd] = tim;
}
void deal(){
int n;
cin>>n;
for(int i = 1; i<n; i++){
int ed;
cin>>ed;
–ed;
g[ed].pb(i);
}
{
int tim = 1;
dfs(0, tim);
}
sums[0] = vector<int>(n, 0);
int q;
cin>>q;
forl(q){
int ty;
cin>>ty;
if(ty == 1){
int vr1, vr2, v, c;
cin>>vr1>>vr2>>v>>c;
--vr1, --vr2, --v;
sums[vr2] = sums[vr1];
fori(n){
if(tin[i] >= tin[v] && tin[i] <= tout[v] && (dep[i] - dep[v]) % 2 == 0){
sums[vr2][i] += c;
}
}
}
else{
int vr, v;
cin>>vr>>v;
--vr, --v;
cout<<sums[vr][v]<<'\n';
}
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
deal();
}