codeforces 696A A. Lorenzo Von Matterhorn(水题)
题目链接:
1 second
256 megabytes
standard input
standard output
Barney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a bidirectional road between intersections i and 2i and another road between i and 2i + 1 for every positive integer i. You can clearly see that there exists a unique shortest path between any two intersections.
Initially anyone can pass any road for free. But since SlapsGiving is ahead of us, there will q consecutive events happen soon. There are two types of events:
1. Government makes a new rule. A rule can be denoted by integers v, u and w. As the result of this action, the passing fee of all roads on the shortest path from u to v increases by w dollars.
2. Barney starts moving from some intersection v and goes to intersection u where there's a girl he wants to cuddle (using his fake name Lorenzo Von Matterhorn). He always uses the shortest path (visiting minimum number of intersections or roads) between two intersections.
Government needs your calculations. For each time Barney goes to cuddle a girl, you need to tell the government how much money he should pay (sum of passing fee of all roads he passes).
The first line of input contains a single integer q (1 ≤ q ≤ 1 000).
The next q lines contain the information about the events in chronological order. Each event is described in form 1 v u w if it's an event when government makes a new rule about increasing the passing fee of all roads on the shortest path from u to v by w dollars, or in form 2 v u if it's an event when Barnie goes to cuddle from the intersection v to the intersection u.
1 ≤ v, u ≤ 10^18, v ≠ u, 1 ≤ w ≤ 10^9 states for every description line.
For each event of second type print the sum of passing fee of all roads Barney passes in this event, in one line. Print the answers in chronological order of corresponding events.
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
94
0
32
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=3e6+;
const int maxn=3e6;
const double eps=1e-; int q;
map<LL,LL>mp,vis;
LL getfa(LL x,LL y)
{
vis.clear();
while(x)vis[x]=,x>>=;
while()
{
if(vis[y])return y;
y>>=;
}
}
int main()
{
read(q);
while (q--)
{
int f;
LL u,v,w;
read(f);
if(f==)
{
read(u);read(v);read(w);
LL fa=getfa(u,v);
while(u!=fa)
{
mp[u]=mp[u]+w;
u>>=;
}
while(v!=fa)
{
mp[v]=mp[v]+w;
v>>=;
}
}
else
{
read(u);read(v);
LL fa=getfa(u,v),ans=;
while(u!=fa)
{
ans+=mp[u];
u>>=;
}
while(v!=fa)
{
ans+=mp[v];
v>>=;
}
print(ans);
}
}
return ;
}
最新文章
- TestNG @Factory与 @DataProvider 结合使用进行参数化测试
- poj 3040 Allowance
- LintCode-Search for a Range
- 【转】oracle查询不到表的问题
- Android处理Bitmap的一些方法
- controller 和 指令 通讯方法
- KEIl混合编程步骤详解
- 哪几个数的阶乘末尾有n个零?
- SVN的revert和update命令的区别
- SQL:多表关联采取这一纪录迄今为止最大
- Objective-C中关于请求返回NSData数据解析成NSDictionary或NSArray的方法
- lufylegend库 LGraphics绘制图片
- 邪恶改装:TPYBoard制作廉价WIFI干扰器
- BOOT BIOS UEFI
- Linux 下 MySQL-5.6.16 安装
- .Net Core实践2 sqlite
- 7.1 C++模板基本概念及语法 《C++模板与标准模板库》
- 结对编程——paperOne基于java的四则运算 功能改进
- [转]OpenStack Neutron解析
- 不同数据库的driverClassName与url
热门文章
- hdu1569 方格取数 求最大点权独立集
- 使用EventNext实现基于事件驱动的业务处理
- 快速掌握RabbitMQ(二)——四种Exchange介绍及代码演示
- 2018 ICPC 徐州网络预赛 Features Track (STL map pair)
- 使用Crypto对数据进行加密解密
- BZOJ1016最小生成树计数 最小生成树 + 排列组合
- Java重写父类使用@Override时出现The method destroy() of type xxx must override a superclass method的问题解决
- SQL Server I/O Basics
- BUPT复试专题—查找(2011)
- 怎样求结构体成员的偏移地址 || 结构体的 sizeof 总结