CF464E The Classic Problem
2022/8/6 23:27:15
本文主要是介绍CF464E The Classic Problem,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
下面的讨论默认 \(n,m,x_i\) 同阶。
这个问题与常规 \(\tt dij\),仅仅差在高精度。而 \(\tt dij\) 所需的高精度如下:
- \(dis_u+w(u,v)\) 中的加法,应该有 \(m\) 次。
- \(dis_u+w(u,v)\) 与 \(dis_v\) 的比较,应该有 \(m\log\) 次。
考虑数据结构维护 \(dis\) 的二进制分解。直接维护空间是 \(\mathcal O(nx)\) 的,但是 \(dis\) 之间互相转移、取 \(\min\),必然有很多位是相同的,于是考虑主席树。
对于加法,
- 找到当前位置之前的连续 \(1\) 总数,这一步可以线段树上二分
- 将这一部分 \(1\) 推平为 \(0\),这一部分可以先维护好一棵全 \(0\) 的线段树,然后使用其中节点替换原主席树的节点即可。
- 在更前一位添加 \(1\),这一部分直接单点修改。
对于比较,
- 同时两个指针遍历两棵线段树
- 如果左子树不同,那么比较左子树,否则比较右子树
- 判断两个子树是否相同,可以维护子树哈希值
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = (a);i <= (b);++i) using hsh = unsigned long long; const int N = 1e5 + 5; const int S = N * 60; const hsh mod = 1e9 + 7; const int X = 1e5 + 50; int n,m,s,t,rt[N],pre[N],dis[N]; bool vis[N]; vector<pair<int,int> > G[N]; hsh pow2[X + 10]; int fa[N],XX; int lc[S],rc[S],cc; hsh w[S]; bool i1[S]; #define mid ((L + R) >> 1) #define ls lc[i],L,mid #define rs rc[i],mid + 1,R void psu(int i,int L,int R){ i1[i] = i1[lc[i]] && i1[rc[i]]; w[i] = (w[rc[i]] * pow2[mid - L + 1] % mod + w[lc[i]]) % mod; } void build(int &i,int L,int R,int x){ i = ++cc; if(L == R) return void(i1[i] = w[i] = x); build(ls,x); build(rs,x); psu(i,L,R); } bool cmp(int i,int j,int L,int R){ if(L == R) return w[i] > w[j]; return w[rc[i]] == w[rc[j]] ? cmp(lc[i],lc[j],L,mid) : cmp(rc[i],rc[j],mid + 1,R); } int fnd(int i,int L,int R){ if(i1[i]) return R; if(L == R) return -1; int _ = fnd(ls); return _ == mid ? max(fnd(rs),mid) : _; } int pos(int i,int L,int R,int p){ if(p <= L) return fnd(i,L,R); if(p > mid) return pos(rs,p); int _ = pos(ls,p); return _ == mid ? max(mid,pos(rs,p)) : _; } struct node{ int u,r; node(int u = 0,int r = 0) : u(u),r(r){} bool operator<(const node &p) const { return cmp(r,p.r,0,XX); } }; void chg(int &p,int i,int j,int L,int R,int l,int r){ if(l <= L && R <= r) return void(p = j); p = ++cc; rc[p] = rc[i]; lc[p] = lc[i]; i1[p] = i1[i]; w[p] = w[i]; if(l <= mid) chg(lc[p],lc[i],lc[j],L,mid,l,r); if(r > mid) chg(rc[p],rc[i],rc[j],mid + 1,R,l,r); psu(p,L,R); } void upd(int &p,int i,int L,int R,int x){ p = ++cc; rc[p] = rc[i]; lc[p] = lc[i]; i1[p] = i1[i]; w[p] = w[i]; if(L == R) return void(i1[p] = w[p] = 1); x <= mid ? upd(lc[p],ls,x) : upd(rc[p],rs,x); psu(p,L,R); } int pls(int rt,int v){ int p = pos(rt,0,XX,v),RT = rt; if(p < 0) p = v - 1; else chg(RT,rt,::rt[0],0,XX,v,p); int ret; upd(ret,RT,0,XX,p + 1); return ret; } priority_queue<node> Q; void dij(){ build(rt[0],0,XX,0); build(rt[n + 1],0,XX,1); rep(i,1,n) rt[i] = rt[n + 1]; Q.emplace(s,rt[s] = rt[0]); while(!Q.empty()){ int u = Q.top().u,r = Q.top().r; Q.pop(); if(vis[u]) continue; vis[u] = 1; if(u == t) return; for(auto e : G[u]){ int v = e.first,w = e.second; int RT = pls(r,w); if(cmp(rt[v],RT,0,XX)){ Q.emplace(v,rt[v] = RT),pre[v] = u; dis[v] = (dis[u] + pow2[w]) % mod; } } } } void print(){ printf("%d\n",dis[t]); deque<int> P; while(t != s) P.push_front(t),t = pre[t]; P.push_front(s); printf("%d\n",P.size()); for(int x : P) printf("%d ",x); printf("\n"); } int fnd(int i){ return i == fa[i] ? i : fa[i] = fnd(fa[i]); } int main(){ scanf("%d%d",&n,&m); rep(i,1,n) fa[i] = i; rep(i,1,m){ int u,v,w; scanf("%d%d%d",&u,&v,&w); fa[fnd(u)] = fnd(v); G[u].emplace_back(v,w); G[v].emplace_back(u,w); XX = max(XX,w); } scanf("%d%d",&s,&t); if(fnd(s) != fnd(t)) return printf("-1\n"),0; pow2[0] = 1; XX += 25; rep(i,1,XX + 2) pow2[i] = (pow2[i - 1] * 2) % mod; dij(); print(); return 0; }
这篇关于CF464E The Classic Problem的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升