C20220712T3 牛半仙的妹子Tree
2022/8/30 23:24:10
本文主要是介绍C20220712T3 牛半仙的妹子Tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定一棵树,要求执行3种操作:
- 给树上某一结点涂色,从下一次操作起每一次向周围传染一个单位。
- 树上所有点变为正常
- 询问某个点是否被感染。
\(n,m\leq 10^5\)。
首先想到暴力做法,用栈维护现在被感染的节点以及感染时间,那么对于操作1,2都好解决,对于操作3需要遍历栈并求出是否有节点可以传染到它(即 \(dis(u,v)\leq time\_now-time\_u\) )。实测可以拿40。
考虑优化思路,可以发现这题的瓶颈在于栈中点太多,那么可以考虑当栈中点过多时可以直接 \(dfs\) 一边,将答案记录在节点上,然后清空,保证对于之前的点可以 \(O(1)\) 查询,同时若出现操作2就直接打上标记,表示之前的点被清空。对于大块整体处理,小块暴力,就是一个类似分块的做法。
struct edge{ ll to,nxt; }e[200005]; struct node{ ll pos,t; node(ll x,ll y){ pos=x; t=y; } node(){pos=0;t=0;} }stabf[100005],sta[100005]; ll head[100005],ecnt; void adde(ll u,ll v){ e[++ecnt].nxt=head[u]; e[ecnt].to=v; head[u]=ecnt; } std::queue<node> q; ll n,m,flag,fa[100005][20],dep[100005],minn[100005],vis[100005];//17 ll top=-1,bj,block,topbf=-1; void dfs(ll x){ dep[x]=dep[fa[x][0]]+1; FOR(i,1,17){ fa[x][i]=fa[fa[x][i-1]][i-1]; } for(rg ll i=head[x];i;i=e[i].nxt){ ll y=e[i].to; if(y==fa[x][0]) continue; fa[y][0]=x; dfs(y); } } void bfs(){ while(q.size()) q.pop(); memset(minn,0x3f,sizeof(minn)); memset(vis,0,sizeof(vis)); FOR(i,0,top){ stabf[++topbf]=sta[i]; } FOR(i,0,topbf){ minn[stabf[i].pos]=std::min(minn[stabf[i].pos],stabf[i].t); } q.push(stabf[0]); ll rr=1; while(q.size()){ node u=q.front(); q.pop(); for(rg ll i=head[u.pos];i;i=e[i].nxt){ int v=e[i].to; if(vis[v]==0){ vis[v]=1; minn[v]=std::min(minn[v],minn[u.pos]+1); q.push(node(v,minn[v])); if(minn[v]==stabf[rr].t){ vis[stabf[rr].pos]=1; q.push(stabf[rr]); ++rr; } } } } } ll dis(ll x,ll y){ ll ret=0; if(dep[x]<dep[y]) std::swap(x,y); ROF(i,17,0){ if(dep[fa[x][i]]>=dep[y]){ ret+=1<<i; x=fa[x][i]; } } ROF(i,17,0){ if(fa[x][i]!=fa[y][i]){ ret+=1<<(1+i); x=fa[x][i]; y=fa[y][i]; } } if(x!=y) ret+=2; return ret; } int main(){ memset(minn,0x3f,sizeof(minn)); n=in(),m=in(); block=900; FOR(i,1,n-1){ ll u=in(),v=in(); adde(u,v); adde(v,u); } dfs(1); FOR(z,1,m){ if(z%block==0){ bfs(); top=-1; bj=0; } ll op=in(),x=in(); if(op==1){ sta[++top]=node(x,z); } if(op==2){ top=-1; topbf=-1; bj=1; } if(op==3){ ll flag=0; FOR(i,0,top){ if(dis(sta[i].pos,x)<=(z-sta[i].t)){ puts("wrxcsd"); flag=1; break; } } if(bj==0 && flag==0){ if(minn[x]<=z){ puts("wrxcsd"); continue; } } if(flag==0){ puts("orzFsYo"); } } } return 0; }
这篇关于C20220712T3 牛半仙的妹子Tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升