304 North Cardinal St.
Dorchester Center, MA 02124

# JosephLand CodeChef Solution

## JosephLand CodeChef Solution in C++14

``````#include <bits/stdc++.h>

using namespace std;
using LL = long long;

#ifdef LOCAL
#include "H:\code\codeforces\debug.h"
#else
#define debug(...)
#define sdebug(...)
#endif

const int N = (int) 1e5 + 5;

vector<pair<LL, LL > > info[N];
vector<LL> curDis;
LL ans[N];

struct ST {
LL tree[4 * N];
static const LL inf = LLONG_MAX;
ST() {
memset(tree, 0, sizeof tree);
}
void update(int node, int b, int e, int i, LL x) {
if (b > i || e < i) return;
if (b == e && b == i) {
tree[node] = x; // update
return;
}
int mid = (b + e) >> 1, l = node << 1, r = l | 1;
update(l, b, mid, i, x);
update(r, mid + 1, e, i, x);
tree[node] = min(tree[l], tree[r]); // change this
}
LL query(int node, int b, int e, int i, int j) {
if (b > j || e < i) return inf; // return appropriate value
if (b >= i && e <= j) return tree[node];
int mid = (b + e) >> 1, l = node << 1, r = l | 1;
return min(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // change this
}
}t;

void dfs(int node, int par) {
if (node == 1) {curDis.push_back(0), t.update(1, 1, N, (int) curDis.size(), ans[node]);}
else {
ans[node] = LLONG_MAX;
for (auto u : info[node]) {
LL cost = u.second, edge = u.first;
LL go = t.query(1, 1, N, max((LL)curDis.size() - edge + 1, 0LL), (int) curDis.size());
ans[node] = min(go + cost, ans[node]);
}
curDis.push_back(ans[node]);
t.update(1, 1, N, (int) curDis.size(), ans[node]);
}
for (int u : adj[node]) {
if (u != par) dfs(u, node);
}
curDis.pop_back();
}

void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i < N; ++i) ans[i] = LLONG_MAX;
for (int i = 1; i <= n - 1; i++) {
int u, v; cin >> u >> v;
}
ans[1] = 0;
for (int i = 1; i <= m; ++i) {
LL u, c, w; cin >> u >> w >> c;
info[u].push_back({w, c}); //edge, cost
}
dfs(1, -1);
int q; cin >> q;
while (q--) {
int node; cin >> node;
cout << ans[node] << "\n";
}
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
}``````

## JosephLand CodeChef Solution in C

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 100000
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;

typedef struct _Ticket {
int dist;
int cost;
} Ticket;

typedef struct _CostSlab {
int start_dist, end_dist;
int cost;
} CostSlab;

typedef struct _City {
#define ALLOC_CHUNK_COUNT 1000
int *arrival_city_ids;
int arrival_id_count, arrival_alloc_count;
Ticket *tickets;
int num_tickets, ticket_alloc_count;
CostSlab *cost_slabs;
int num_cslabs, cslab_alloc_count;
int max_dist; // max distance that can be reached from here using any ticket
ll min_cost; // min cost to capital
} City;

City cities[NMAX] = {0};
int path_city_ids[NMAX];
ll path_min_costs[NMAX];

int Ticket_cmp(const void *p1, const void *p2)
{
Ticket *t1, *t2;
t1 = (Ticket *)p1;
t2 = (Ticket *)p2;
if (t1->cost != t2->cost)
return t1->cost - t2->cost;
return t2->dist - t1->dist; // for same cost, more distance is better
}

#define MAX_PO2 32
int po2_max; // actual
ll *min_arr[MAX_PO2 + 1];
ll *min_arr_chunk_data[MAX_PO2 + 1];

ll get_min_cost(ll *arr, int L, int R)
{
int chunk_size = R - L + 1;
if (chunk_size == 1)
return arr[L];
if (chunk_size == 2)
return min(arr[L], arr[R]);
int po2;
for (po2 = po2_max; (1 << po2) > chunk_size; )
po2--;
int po2_sz = (1 << po2);
int div = L / po2_sz;
if (L % po2_sz)
div++;
ll min_val = -1, min_part1 = -1;
int br1 = div * po2_sz;
if (br1 + po2_sz - 1 > R) {
// po2 chunk not contained
po2--;
po2_sz = (1 << po2);
div = L / po2_sz;
if (L % po2_sz)
div++;
br1 = div * po2_sz;
}
if (br1 > L)
min_val = min_part1 = get_min_cost(arr, L, br1 - 1);
ll min_part2 = min_arr[po2][div];
if (min_val == -1 || min_part2 < min_val)
min_val = min_part2;
int br2 = br1 + po2_sz;
ll min_part3 = -1;
if (br2 <= R) {
min_part3 = get_min_cost(arr, br2, R);
if (min_val == -1 || min_part3 < min_val)
min_val = min_part3;
}
return min_val;
}

void traverse_cities(int id, int N, int dist_from_capital, int *path_city_ids, ll *path_min_costs)
{
static int min_arr_initialized = 0;
int po2, chunk_sz, num_chunks;
if (!min_arr_initialized) {
for (po2 = 1; po2 <= MAX_PO2; po2++) {
chunk_sz = (1 << po2);
if (chunk_sz > N)
break;
po2_max = po2;
num_chunks = N / chunk_sz + ((N % chunk_sz) ? 1 : 0);
min_arr[po2] = (ll *)malloc(num_chunks * sizeof(ll));
min_arr_chunk_data[po2] = (ll *)malloc(num_chunks * chunk_sz * sizeof(ll));
}
min_arr_initialized = 1;
}
City *cp = &cities[id];
int i;
if (id == 0)
cp->min_cost = 0;
else {
ll min_cost = -1;
int prev_sz = 0;
for (i = 0; i < cp->num_cslabs; i++) {
CostSlab *cslabp = &cp->cost_slabs[i];
int slab_dist = cslabp->end_dist - cslabp->start_dist + 1;
int path_start_i = dist_from_capital - slab_dist - prev_sz;
if (path_start_i < 0)
path_start_i = 0;
int seg_count = min(dist_from_capital, slab_dist);
int path_end_i = path_start_i + seg_count - 1;
ll this_cost = get_min_cost(path_min_costs, path_start_i, path_end_i) + (ll)cslabp->cost;
if (min_cost == -1 || this_cost < min_cost)
min_cost = this_cost;
prev_sz = seg_count;
if (path_start_i == 0)
break;
}
cp->min_cost = min_cost;
}
path_city_ids[dist_from_capital] = id;
path_min_costs[dist_from_capital] = cp->min_cost;
for (po2 = 1; po2 <= po2_max; po2++) {
chunk_sz = (1 << po2);
int chunk_i = dist_from_capital / chunk_sz;
int i_in_chunk = dist_from_capital % chunk_sz;
if (i_in_chunk == 0) {
min_arr[po2][chunk_i] = min_arr_chunk_data[po2][chunk_i * chunk_sz] = cp->min_cost;
} else {
int ind_chunk_data = chunk_i * chunk_sz + i_in_chunk;
min_arr[po2][chunk_i] = min_arr_chunk_data[po2][ind_chunk_data] = min(min_arr_chunk_data[po2][ind_chunk_data - 1], cp->min_cost);
}
}
for (i = 0; i < cp->arrival_id_count; i++)
traverse_cities(cp->arrival_city_ids[i], N, dist_from_capital + 1, path_city_ids, path_min_costs);
}

int main()
{
int N, M, i, j;
scanf("%d %d", &N, &M);
for (i = 0; i < N - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
cities[b - 1].arrival_id_count++;
if (cities[b - 1].arrival_id_count > cities[b - 1].arrival_alloc_count) {
cities[b - 1].arrival_alloc_count += ALLOC_CHUNK_COUNT;
if (!cities[b - 1].arrival_city_ids)
cities[b - 1].arrival_city_ids = (int *)malloc(cities[b - 1].arrival_alloc_count * sizeof(int));
else
cities[b - 1].arrival_city_ids = (int *)realloc(cities[b - 1].arrival_city_ids,
cities[b - 1].arrival_alloc_count * sizeof(int));
}
cities[b - 1].arrival_city_ids[cities[b - 1].arrival_id_count - 1] = a - 1;
}
for (i = 0; i < M; i++) {
int v, k, w;
scanf("%d %d %d", &v, &k, &w);
City *cp = &cities[v - 1];
cp->num_tickets++;
if (cp->num_tickets > cp->ticket_alloc_count) {
cp->ticket_alloc_count += ALLOC_CHUNK_COUNT;
if (!cp->tickets)
cp->tickets = (Ticket *)malloc(cp->ticket_alloc_count * sizeof(Ticket));
else
cp->tickets = (Ticket *)realloc(cp->tickets, cp->ticket_alloc_count * sizeof(Ticket));
}
Ticket *tp = cp->tickets + cp->num_tickets - 1;
tp->dist = k;
tp->cost = w;
}
// process tickets info
for (i = 0; i < N; i++) {
City *cp = &cities[i];
qsort(cp->tickets, cp->num_tickets, sizeof(Ticket), Ticket_cmp);
int max_dist = 0;
for (j = 0; j < cp->num_tickets; j++) {
Ticket *tp = &cp->tickets[j];
if (tp->dist <= max_dist)
continue;
cp->num_cslabs++;
if (cp->num_cslabs > cp->cslab_alloc_count) {
cp->cslab_alloc_count += ALLOC_CHUNK_COUNT;
if (!cp->cost_slabs)
cp->cost_slabs = (CostSlab *)malloc(cp->cslab_alloc_count * sizeof(CostSlab));
else
cp->cost_slabs = (CostSlab *)realloc(cp->cost_slabs, cp->cslab_alloc_count * sizeof(CostSlab));
}
CostSlab *cslabp = cp->cost_slabs + cp->num_cslabs - 1;
cslabp->start_dist = max_dist + 1;
cslabp->end_dist = max_dist = tp->dist;
cslabp->cost = tp->cost;
}
cp->max_dist = max_dist;
}
// traverse cities
traverse_cities(0, N, 0, path_city_ids, path_min_costs);

int Q;
scanf("%d", &Q);
while (Q--) {
int h;
scanf("%d", &h);
printf("%lld\n", cities[h - 1].min_cost);
}

return 0;
}``````

## JosephLand CodeChef Solution in JAVA

``````/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{

public static void main(String[] args) {

try {
int n=Integer.parseInt(s[0]);
int m=Integer.parseInt(s[1]);

for(int i=0;i<n-1;i++) {
int p=Integer.parseInt(s[0])-1;
int q=Integer.parseInt(s[1])-1;

}

for(int i=0;i<m;i++) {
int p=Integer.parseInt(s[0])-1;
int q=Integer.parseInt(s[1]);
int r=Integer.parseInt(s[2]);

int ar[]= {q,r};
}

long a[]=new long[n];
long tree[]=new long[4*n+1];
Arrays.fill(a, Long.MAX_VALUE);
Arrays.fill(tree, Long.MAX_VALUE);

dfs(tree,0,a,0);

StringBuilder sb=new StringBuilder();
while(q-->0) {
sb.append(a[p]+"\n");
}
System.out.println(sb);
}
catch(Exception e) {
return;
}

}

static void dfs(long tree[],int pos,long a[],int cur) {

int n=a.length;
long min=Long.MAX_VALUE;

for(int[] i:tickets[cur]) {
long tempMin=i[1];
int l=pos-i[0]<0?0:pos-i[0];
int r=pos-1;

tempMin+=query(tree,1,0,n-1,l,r);

min=Long.min(min, tempMin);
}

update(tree,1,0,n-1,pos,pos==0?0:min);
a[cur]=min;
if(pos==0)	a[cur]=0;

dfs(tree,pos+1,a,i);
}
update(tree,1,0,n-1,pos,Long.MAX_VALUE);
}

static long query(long tree[],int i,int s,int e,int qs,int qe) {

if(qs>e || qe<s) {
return Long.MAX_VALUE;
}

if(qs<=s && qe>=e) {
return tree[i];
}

int mid=s+e>>1;
return Long.min(query(tree,2*i,s,mid,qs,qe), query(tree,2*i+1,mid+1,e,qs,qe));
}

static void update(long tree[],int ind,int s,int e,int i,long val) {

if(i<s || i>e) {
return;
}

if(s==e) {
tree[ind]=val;
return;
}

int mid=s+e>>1;
update(tree,2*ind,s,mid,i,val);
update(tree,2*ind+1,mid+1,e,i,val);
tree[ind]=Long.min(tree[2*ind], tree[2*ind+1]);
return;
}

}``````

## JosephLand CodeChef Solution in PYTH

``````import sys
from math import log,ceil
sys.setrecursionlimit(1000005)
inf=pow(10,18)
def update(idx,low,high,pos,val):
if idx<low or idx>high:
return
if low==high:
st[pos]=val
return
mid=(low+high)>>1
if idx<=mid:
update(idx,low,mid,2*pos+1,val)
else:
update(idx,mid+1,high,2*pos+2,val)
st[pos] = min(st[2 * pos + 1], st[2 * pos + 2])

def query(qlow, qhigh, low, high, pos):
if qlow <= low and qhigh >= high: #TOTAL OVERLAP
return st[pos]
if qlow > high or qhigh < low: #NO OVERLAP
return inf
mid = (low + high)>>1
#PARTIAL OVERLAP
left=query(qlow, qhigh, low, mid, 2 * pos + 1)
right=query(qlow, qhigh, mid+1, high, 2 * pos + 2)
return min(left,right)

def dfs(cur_node,depth):
if cur_node!=0:
for k,w in tickets[cur_node]:
dp[cur_node]=min(dp[cur_node],query(max(0,depth-k),depth,0,n-1,0)+w)
update(depth,0,n-1,0,dp[cur_node])
for v in tree[cur_node]:
dfs(v,depth+1)
update(depth,0,n-1,0,inf)

author="tanmoy khatua"
aa,bb=0,0
n,m=map(int,raw_input().split())
tree=[[] for i in xrange(n)]
for i in xrange(n-1):
a,b=map(int,raw_input().split())
tree[b-1].append(a-1)
tickets=[[] for i in xrange(n)]
for i in xrange(m):
v,k,w=map(int,raw_input().split())
tickets[v-1].append((k,w))
dp=[inf for i in xrange(n)]
dp[0]=0
st=[inf for i in xrange(5*n)]
update(0,0,n-1,0,0)
dfs(0,0)
q=input()
for i in xrange(q):
print dp[input()-1]``````

## JosephLand CodeChef Solution in C#

``````using Boilerplate.IO;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

public class Solver
{

{
this.writer = writer;
}

public void Generate()
{ }

public void RmqUpdate(long[][] store, int level, int pos, long val)
{
store[0][pos] = val;
for (int i = 1; i < level; ++i)
{
pos >>= 1;
store[i][pos] = store[i - 1][pos << 1];
if ((pos << 1) + 1 < store[i - 1].Length)
store[i][pos] = Math.Min(store[i][pos], store[i - 1][(pos << 1) + 1]);
}
}

public long RmqGet(long[][] store, int level, int l, int r)
{
long res = long.MaxValue;
for (int i = 0; i < level && l <= r; ++i)
{
if ((l & 1) == 1)
res = Math.Min(res, store[i][l]);
l = (l + 1) >> 1;
if ((r & 1) == 0)
res = Math.Min(res, store[i][r]);
r = (r - 1) >> 1;
}
return res;
}

int[] child;
int[] next;
long[] cost;
Dictionary<int, List<Tuple<int, int>>> tcts;

int DEPTH = 17;
long[][] stack;

public void Dfs(int node, int level)
{
if (level > 0 && tcts.ContainsKey(node))
{
var best = long.MaxValue;
foreach (var tpl in tcts[node])
{
var val = RmqGet(stack, DEPTH, Math.Max(0, level - tpl.Item1), level - 1);
best = Math.Min(best, val + tpl.Item2);
}
RmqUpdate(stack, DEPTH, level, cost[node] = best);
}
else
cost[node] = 0;
var chld = child[node];
while (chld != -1)
{
Dfs(chld, level + 1);
chld = next[chld];
}
}

public void Do()
{
child = new int[n];
next = new int[n];
cost = new long[n];
tcts = new Dictionary<int, List<Tuple<int, int>>>();
stack = new long[DEPTH][];
for (int i = 0; i < DEPTH; ++i)
{
stack[i] = new long[n + 1];
}
RmqUpdate(stack, DEPTH, n, long.MaxValue);
for (int i = 0; i < n; ++i)
child[i] = -1;
for (int i = 0; i < n - 1; ++i)
{
next[a] = child[b];
child[b] = a;
}
for (int i = 0;i < m; ++i)
{
if (!tcts.ContainsKey(v))
tcts[v] = new List<Tuple<int, int>>();
}
Dfs(0, 0);
while (q-- > 0)
{
writer.WriteLine(cost[fr]);
}
}
}

#region launch
class Program
{
static void Main(string[] args)
{
using (var writer = new FormattedStreamWriter(
#if SOLVER_RUN_LOCAL
"output.txt"
#else
Console.OpenStandardOutput()
#endif
))
{
#if SOLVER_RUN_LOCAL
"input.txt"
#else
Console.OpenStandardInput()
#endif
))
{
#if SOLVER_RUN_LOCAL
var stopw = new Stopwatch();
stopw.Start();
#endif
#if SOLVER_RUN_LOCAL
stopw.Stop();
writer.WriteLine("> {0}ms", stopw.ElapsedMilliseconds);
#endif
}
}
}
}
#endregion

namespace Boilerplate.IO
{
#region helpers
class FormattedStreamWriter : StreamWriter
{
public FormattedStreamWriter(Stream stream) : base(stream) { }
public FormattedStreamWriter(string filePath) : base(filePath) { }
public override IFormatProvider FormatProvider
{
get
{
return CultureInfo.InvariantCulture;
}
}
}
static class IOExtensions
{
{
}
{
}
{
}
{
}
{
}

static Queue<string> buffer = new Queue<string>(100);
{
while (buffer.Count == 0)
{
{
buffer.Enqueue(t);
});
} return buffer.Dequeue();
}
}
#endregion
}``````

## JosephLand CodeChef Solution in GO

``````package main
import ("fmt"; "bufio"; "os")

const (
MAXN = 100000
INF = int64(1e17)
)

//----------------------------------------------------------
type City struct {
parent int
costToRoot int64
children []int
tickets []Ticket
}

type Ticket struct {
cost int
uses int
}

var cities []City

func initCities(N int) {
cities = make([]City, N)
for i:=0; i<N; i++ {
cities[i].children = make([]int, 0, 2)
cities[i].tickets = make([]Ticket, 1)
}
}

func maxLevel(idx int) int {
maxlvl := 0
for _, ch := range cities[idx].children {
maxlvl = max(maxlvl, maxLevel(ch))
}
return 1+maxlvl
}

//----------------------------------------------------------
type Interval struct {
l, r int
}

func (this Interval) disjoint(other Interval) bool {
return this.r<other.l || this.l>other.r
}

func (this Interval) insideOf(other Interval) bool {
return this.l>=other.l && this.r<=other.r
}

func (this Interval) contains(pos int) bool {
return this.l <= pos && pos <= this.r
}

var tree []int64

func childrenIndex(nodeIdx int, ivlTree Interval) (lchild, rchild, mid int) {
lchild = 2*nodeIdx+1
rchild = 2*nodeIdx+2
mid = (ivlTree.l + ivlTree.r)/2
return
}

func initSegmentTree(size int) {
tree = make([]int64, 4*size)
}

func query(nodeIdx int, ivlTree, ivlQuery Interval) int64 {
if(ivlTree.disjoint(ivlQuery)) {
return INF
}

if ivlTree.insideOf(ivlQuery) {
return tree[nodeIdx]
}

var lchild, rchild, mid = childrenIndex(nodeIdx, ivlTree)
var lv = query(lchild, Interval{ivlTree.l,   mid}, ivlQuery)
var rv = query(rchild, Interval{mid+1, ivlTree.r}, ivlQuery)
return min(lv, rv)
}

func update(nodeIdx int, ivlTree Interval, pos int, newval int64) {
if !ivlTree.contains(pos) {
return
}

if ivlTree.l==ivlTree.r {
if ivlTree.l != pos {
}
tree[nodeIdx] = newval
return
}

var lchild, rchild, mid = childrenIndex(nodeIdx, ivlTree)
update(lchild, Interval{ivlTree.l,   mid}, pos, newval)
update(rchild, Interval{mid+1, ivlTree.r}, pos, newval)
tree[nodeIdx] = min(tree[lchild], tree[rchild])
}

func querySegment(l, r int) int64 {
return query(0, Interval{0, len(cities)-1}, Interval{l, r});
}

func solveCity(cityIdx, level int) {
best := INF
if cityIdx == 0 {
best = 0
} else {
for _, ticket := range cities[cityIdx].tickets {
best = min(best, int64(ticket.cost)+querySegment(level-ticket.uses, level-1))
}
}
//println(best)
cities[cityIdx].costToRoot = best
update(0, Interval{0, len(cities)-1}, level, best)

for _, ch := range cities[cityIdx].children {
solveCity(ch, level+1)
}
}

func main() {
scanner.Split(bufio.ScanWords)
var out = bufio.NewWriter(os.Stdout)
defer out.Flush()

initCities(N)

for i:=0; i<N-1; i++ {
cities[a].parent = b
cities[b].children = append(cities[b].children, a)
}

for i:=0; i<M; i++ {
cities[v].tickets = append(cities[v].tickets, Ticket{w, k})
}

initSegmentTree(maxLevel(0)+1)
solveCity(0, 0)

//fmt.Fprintf(out, "%v", mindist);

fmt.Fprintln(out, cities[h].costToRoot)
}
}

//--------------------------------------------------------------
var scanner *bufio.Scanner

if !scanner.Scan() {
panic(fmt.Sprintf("Error scanning: %v", scanner.Err()))
}
return scanner.Bytes()
}

var num = 0
for i:=0; i<len(bs); i++ {
digit := bs[i]
if digit<'0' || digit>'9' {
panic(fmt.Sprintf("Not a digit: %c", digit))
}
num = num*10 + int(digit-'0')
}
return num
}

func min(a, b int64) int64 {
if a<b {
return a
} else {
return b
}
}

func max(a, b int) int {
if a>b {
return a
} else {
return b
}
}``````
##### JosephLand CodeChef Solution Review:

In our experience, we suggest you solve this JosephLand CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the JosephLand CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this JosephLand CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!