「小奇模拟赛2」小奇的危机
「题目背景」
小奇驾驶飞船来到了一个奇怪的星球，这个星球的所以城市都在地下，而且由于环境不断恶化，星球上发生了可怕的生化危机。
「问题描述」
星球上有n个城市，标号为1-n，用n-1条双向通道连接，保证任意两个城市能互相到达。
生化危机爆发了！但由于政府安全能力有限，安全区只包括在标号l到r的城市，小奇现在在城市x，它想知道最近的安全城市的距离。
「输入格式」
第一行有1个整数n。
接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的双向通道。
接下来1个整数q，表示q次生化危机。
接下来q行，每行3个整数l，r，x，描述一次生化危机。
「输出格式」
输出q行，对于每次生化危机输出1个整数，表示最近安全城市的距离。
「样例输入」
3
1 2 1
1 3 1
3
2 3 1
2 3 2
3 3 2
「样例输出」
1
0
2
「数据范围」
对于30%的数据, n，q<=1000；
另有20%的数据，保证第城市2-n均可直接到达城市1；
另有10%的数据，保证城市i(1<=i<=n-1)可直接到达城市i+1；
对于100%的数据, n，q<=100000，li<=ri，任意两个城市的距离小于10^9。
「题解」
本题来自吉大附中wyf
对于30%的数据，暴力模拟
对于菊花图，分类讨论一下询问点是不是1号点，用rmq维护一段区间到1号点的最短距离。
一条链维护前缀和贪心。
对于100%的数据
1.分块！？
恩解决了。？能卡过、、
预处理每个点要走多远能到达某个块内的点，对于询问整块调用预处理答案，剩下暴力。
2.线段树
每一个线段树结点维护一棵区间内的标号的点形成的虚树，对于每次询问，拆分成logn段区间，然后分别询问。
将询问离线处理，不妨将询问点都插入区间虚树中，然后对每个线段树的结点一次树形dp来计算答案。
线段树结点中虚树总点数为(n+q)logn，加上构建虚树的复杂度，总复杂度(n+q)log^2n
分块（常数大的飞起）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define pi acos(-1) #define eps 1e-13 #define mod 10000007 #define inf 2147483647 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,Q,blo,cnt,dfn; int bin[20],Log[200005]; int last[100005],bl[100005],depth[100005],dis[100005]; int mn[18][200005],pos[100005]; int dp[205][100005]; struct edge{ int to,next,v; }e[200005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],w};last[v]=cnt; } void dfs(int x,int fa) { mn[0][++dfn]=x; pos[x]=dfn; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { depth[e[i].to]=depth[x]+1; dis[e[i].to]=dis[x]+e[i].v; dfs(e[i].to,x); mn[0][++dfn]=x; } } int rmq(int x,int y) { x=pos[x];y=pos[y]; if(y<x)swap(x,y); int t=Log[y-x+1]; if(depth[mn[t][x]]<depth[mn[t][y-bin[t]+1]]) return mn[t][x]; else return mn[t][y-bin[t]+1]; } int getdis(int x,int y) { return dis[x]+dis[y]-2*dis[rmq(x,y)]; } priority_queue<pa,vector<pa>,greater<pa> >pq; bool vis[100005]; void bfs(int id) { while(!pq.empty()) { int now=pq.top().second;pq.pop(); if(vis[now])continue;vis[now]=1; for(int i=last[now];i;i=e[i].next) if(dp[id][now]+e[i].v<dp[id][e[i].to]||!dp[id][e[i].to]) { dp[id][e[i].to]=dp[id][now]+e[i].v; pq.push(make_pair(dp[id][e[i].to],e[i].to)); } } } void pre() { dfs(1,0); for(int i=1;i<=Log[dfn];i++) for(int j=1;j<=dfn;j++) if(j+bin[i]-1<=dfn) { if(depth[mn[i-1][j]]<depth[mn[i-1][j+bin[i-1]]]) mn[i][j]=mn[i-1][j]; else mn[i][j]=mn[i-1][j+bin[i-1]]; } for(int i=1;i<=bl[n];i++) { memset(vis,0,sizeof(vis)); for(int j=(i-1)*blo+1;j<=min(n,i*blo);j++) dp[i][j]=1,pq.push(make_pair(1,j)); bfs(i); } } void query(int l,int r,int x) { int L=bl[l],R=bl[r],ans=inf; if(L==R) for(int i=l;i<=r;i++) ans=min(ans,getdis(x,i)); else { for(int i=l;bl[i]==L;i++) ans=min(ans,getdis(x,i)); for(int i=r;bl[i]==R;i--) ans=min(ans,getdis(x,i)); for(int i=L+1;i<=R-1;i++) ans=min(ans,dp[i][x]-1); } printf("%d\n",ans); } int main() { freopen("crisis.in","r",stdin); freopen("crisis.out","w",stdout); bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; Log[0]=-1;for(int i=1;i<=200000;i++)Log[i]=Log[i>>1]+1; n=read(); blo=500; for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1; for(int i=1;i<=n-1;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } pre(); Q=read(); while(Q--) { int l=read(),r=read(),x=read(); query(l,r,x); } return 0; } |
OI 课件=>
