Skip to content

Instantly share code, notes, and snippets.

@codekansas
Last active July 17, 2016 00:22
Show Gist options
  • Save codekansas/bfa6ec46d24e5196aa49b2a13e0e3b84 to your computer and use it in GitHub Desktop.
Save codekansas/bfa6ec46d24e5196aa49b2a13e0e3b84 to your computer and use it in GitHub Desktop.
// reference: http://codeforces.com/contest/697/problem/C
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Codeforces697ProblemC {
public static void main(String... args) {
Scanner s = new Scanner(System.in);
costs = new HashMap<>();
final int Q = s.nextInt();
long u, v, w;
for (int q = 0; q < Q; q++) {
if (s.nextInt() == 1) {
u = s.nextLong();
v = s.nextLong();
w = s.nextLong();
updateCosts(u, v, w);
} else {
u = s.nextLong();
v = s.nextLong();
solve(u, v);
}
}
s.close();
}
static Map<Long, Long> costs;
static void solve(long u, long v) {
long c = commonAncestor(u, v), cost = 0;
while (u != c) {
cost += costs.containsKey(u) ? costs.get(u) : 0;
u /= 2;
}
while (v != c) {
cost += costs.containsKey(v) ? costs.get(v) : 0;
v /= 2;
}
System.out.println(cost);
}
static void updateCosts(long u, long v, long w) {
long c = commonAncestor(u, v);
while (u != c) {
if (costs.containsKey(u)) {
costs.put(u, costs.get(u) + w);
} else {
costs.put(u, w);
}
u /= 2;
}
while (v != c) {
if (costs.containsKey(v)) {
costs.put(v, costs.get(v) + w);
} else {
costs.put(v, w);
}
v /= 2;
}
}
static long commonAncestor(long a, long b) {
while (a != b) {
while (a > b) {
a /= 2;
}
while (b > a) {
b /= 2;
}
}
return a;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment