关键词:
1553. Caves and Tunnels
Memory limit: 64 MB
Input
Output
Sample
input | output |
---|---|
4 1 2 2 3 2 4 6 I 1 1 G 1 1 G 3 4 I 2 3 G 1 1 G 3 4 |
1 0 1 3 |
Tags: data structures
)
瞬秒~~
题目大意:一棵树,開始每一个点权的权值为0,后边q次操作。I a b,a点点权加b。G a b查询从a到b要走的最大的权值
ac代码
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> #define INF 0x7fffffff #define max(a,b) (a>b?a:b) using namespace std; int vis[100050]; struct LCT { int bef[100050],pre[100050],next[100050][2],key[100050],val[100050]; void init() { memset(pre,0,sizeof(pre)); memset(next,0,sizeof(next)); memset(key,0,sizeof(key)); val[0]=-INF; } void pushup(int x) { val[x]=max(key[x],max(val[next[x][1]],val[next[x][0]])); } void rotate(int x,int kind) { int y,z; y=pre[x]; z=pre[y]; next[y][!kind]=next[x][kind]; pre[next[x][kind]]=y; next[z][next[z][1]==y]=x; pre[x]=z; next[x][kind]=y; pre[y]=x; pushup(y); } void splay(int x) { int rt; for(rt=x;pre[rt];rt=pre[rt]); if(x!=rt) { bef[x]=bef[rt]; bef[rt]=0; while(pre[x]) { if(next[pre[x]][0]==x) { rotate(x,1); } else rotate(x,0); } pushup(x); } } void access(int x) { int fa; for(fa=0;x;x=bef[x]) { splay(x); pre[next[x][1]]=0; bef[next[x][1]]=x; next[x][1]=fa; pre[fa]=x; bef[fa]=0; fa=x; pushup(x); } } void change(int x,int y) { key[x]+=y; splay(x); } int query(int x,int y) { access(y); for(y=0;x;x=bef[x]) { splay(x); if(!bef[x]) { return max(key[x],max(val[next[x][1]],val[y])); } pre[next[x][1]]=0; bef[next[x][1]]=x; next[x][1]=y; pre[y]=x; bef[y]=0; y=x; pushup(x); } return 0; } }lct; struct s { int u,v,next; }edge[200020<<1]; int head[200020],cnt; void add(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void bfs(int u) { queue<int>q; memset(vis,0,sizeof(vis)); vis[u]=1; q.push(u); while(!q.empty()) { u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { lct.bef[v]=u; vis[v]=1; q.push(v); } } } } int main() { int n; while(scanf("%d",&n)!=EOF) { int i=1; memset(head,-1,sizeof(head)); cnt=0; for(i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } int q; scanf("%d",&q); lct.init(); bfs(1); while(q--) { char str[2]; int u,v; scanf("%s%d%d",str,&u,&v); if(str[0]==‘I‘) lct.change(u,v); else printf("%d ",lct.query(u,v)); } } }
ural1104,暴力取模
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1104题目大意:输入一个字符串(数字与大写字母组成),输出n,n满足此字符串为n进制时,其n进位制数能被n-1整除(n不存在时输出"Nosolution"(不包括双引号))。 题目好多坑点... 查看详情
ural1823.idealgas(数学啊)
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=18231823.IdealGasTimelimit:0.5secondMemorylimit:64MBManyofyouknowtheuniversalmethodofsolvingsimplephysicsproblems:youhavetofindinatextbookanidenti 查看详情
ural1682crazyprofessor(并查集)
【题目链接】 http://acm.timus.ru/problem.aspx?space=1&num=1682 【题目大意】 给出k,从1开始不断地加一并把这个数写在黑板上,如果写上的数字和之前的数字满足 (a+b*b)%k=0或者(b+a*a)%k=0就在他们之间连一条线,如果... 查看详情
ural-1902neo-venice
题目:Marswasthefirstplanetcolonizedbyhumans.Afteralongterraformingprocessitsappearancehaschangedcompletely.Fromthereddesertithasbecomeablueplanetcoveredbywater.Therewassomuchwaterthatsomeofthecitieswere 查看详情
ural2078~2089
URAL2078~2089A-Bowlinggame题目描述:给出保龄球每一局击倒的球数,按照保龄球的规则,算出总得分的最小值和最大值。solution首先是最小值:每一局第一球击倒(0)个,第二球击倒给定的数目,最后一局比较特殊,如果最后一局得分... 查看详情
ural1982.electrificationplan(并查集)
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1982Somecountryhas n cities.Thegovernmenthasdecidedtoelectrifyallthesecities.Atfirst,powerstationsin k differentcitieswerebuil 查看详情
ural2018thedebutalbum(dp)
题目地址:Ural2018简单DP。用滚动数组。代码例如以下:#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<stdlib.h>#include<math.h>#include<ctype.h>#include& 查看详情
ural1707.hypnotoad'ssecret(线段树)
题目链接:ural1707.Hypnotoad‘sSecret题目大意:给定N和M,然后N组s0,t0,Δs,Δt,k,每组能够计算出k个星星的坐标;M组a0,b0,c0,d0,Δa,Δb,Δc,?Δd,q。每组要求算出q个矩形,推断矩形内是否包括星星,对于q≥20的情况要依据公式计算一个值... 查看详情
ural1519:formula1——题解
http://acm.timus.ru/problem.aspx?space=1&num=1519https://vjudge.net/problem/URAL-1519题目大意:给一个网格,有些网格有障碍,问有多少条哈密顿回路。———————————&mda 查看详情
ural1297palindrome(后缀数组+st表)
【题目链接】 http://acm.timus.ru/problem.aspx?num=1297 【题目大意】 求最长回文子串,并输出这个串。 【题解】 我们将原串倒置得到一个新的串,加一个拼接符将新串拼在原串的后面, 那么枚举对称的中心... 查看详情
ural1113,jeepproblem
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1113网上的解答铺天盖地。我硬是花了两天才懂了点。wiki上的解释:https://en.wikipedia.org/wiki/Jeep_problem 解答:每个点的油量是500,500*2,500*3......每次的距离是500,500/3,500/5,......... 查看详情
ural1303minimalcoverage(贪心)
题目地址:Ural1303先按每一个线段的左端点排序,然后设置一个起点s。每次都从起点小于等于s的线段中找到一个右端点最大的。并将该右端点作为新的起点s,然后继续找。从左到右扫描一遍就可以。代码例如以下:#include<iost... 查看详情
ural2052physicaleducation(代码片段)
题目链接:https://vjudge.net/contest/254142#problem/G参考题解:https://blog.csdn.net/zearot/article/details/47984379 1#include<bits/stdc++.h>2usingnamespacestd;3#definelllonglong4#defineLL__int1285#d 查看详情
ural-1078segments
URAL-1078 题目大意:有n条线段,一个线段a完全覆盖另一个线段b当且仅当,a.l<b.l&&a.r>b.r。问你一个线段覆盖一个线段再覆盖一个线段再.......,问你最多几个线段属于这种关系,并打印出路径。 这题的的n太小了... 查看详情
ural2040palindromesandsuperabilities2
题目太坑,发一波纪念一下1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=5000010;5structPAM{6intcnt,last;7inta[N][2],l[N],f[N];8chars[N];9PAM(){10cnt=f[0]=f[1]=1;11l[1]=-1;12}13intge 查看详情
ural1750pakhomandthegully计算几何+floyd
题目链接:点击打开链接gg。。。#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<iostream>#include<algorithm>#include<string.h>#include<vector>#include<qu 查看详情
ural1112,lis
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1112题意:n根线段,要拿走一些,使得任何的线段的左段没有在某一个线段的内部。其实说白了,就是拿走最少的线段,使得不重合。数据量很小,100,直接LISO(n^2)搞。首先按x从... 查看详情
ural1903unidentifiedships组合数+乘法逆元
一開始题意没读懂。英语是硬伤,事实上是这道题目真的有点饶人,后来补题,看懂了意思。从n个数中挑出t个,然后第k个必需要在,挑出的t个数要排序成不下降的顺序,然后原本那个第k个数在这个跳出的t个数其中要在第x的... 查看详情