3712: [PA2014]Fiolki
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 269 Solved: 57
[Submit][Status][Discuss]
Description
化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有n种不同的液体物质，和n个药瓶（均从1到n编号）。初始时，第i个瓶内装着g[i]克的第i种物质。吉丽需要执行一定的步骤来配置药水，第i个步骤是将第a[i]个瓶子内的所有液体倒入第b[i]个瓶子，此后第a[i]个瓶子不会再被用到。瓶子的容量可以视作是无限的。
吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是1克c[i]物质和1克d[i]物质生成2克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。
吉丽想知道配置过程中总共产生多少沉淀。
Input
第一行三个整数n,m,k(0<=m<n<=200000,0<=k<=500000)，分别表示药瓶的个数（即物质的种数），操作步数，可以发生的反应数量。
第二行有n个整数g[1],g[2],…,g[n]（1<=g[i]<=10^9)，表示初始时每个瓶内物质的质量。
接下来m行，每行两个整数a[i],b[i](1<=a[i],b[i]<=n,a[i]≠b[i])，表示第i个步骤。保证a[i]在以后的步骤中不再出现。
接下来k行，每行是一对可以发生反应的物质c[i],d[i](1<=c[i],d[i]<=n,c[i]≠d[i])，按照反应的优先顺序给出。同一个反应不会重复出现。
Output
Sample Input
2 3 4
1 2
3 2
2 3
Sample Output
HINT
Source
因为没有写>=所以倍增lca炸了一下午。。。调了两节课感觉爽爽哒。。。
先对所有的操作建一棵树。。两种溶液混合就新建一个点把两种溶液的父亲指向他。。
然后对所有询问中的两个点求lca。。然后按照深度排序。。然后就好了。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
using namespace std;
const ll N = 400010;
struct data{ll x,y,ans,id;} q[500010];
struct node{ll x,y,next;} e[N];
ll deep[N],fa[N][30],f[N],head[N],n,m,k,x,y,cnt,g[N],used[N];
long long sum;
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
bool cmp(data a,data b){if (a.ans==b.ans) return a.id<b.id;return a.ans>b.ans;}
void Insert(ll x,ll y){
e[++cnt].x = x;e[cnt].y = y;
e[cnt].next = head[x];head[x] = cnt;
}
void dfs(ll x,ll Fa){
for (ll i=1;i<=28;i++){
if (deep[x]<(1<<i)) break;
fa[x][i] = fa[fa[x][i-1]][i-1];
}
for (ll i=head[x];i;i=e[i].next)
if (e[i].y!=Fa){
deep[e[i].y] = deep[x]+1;
fa[e[i].y][0] = x;
dfs(e[i].y,x);
}
}
ll lca(ll x,ll y){
if (deep[x]<deep[y]) swap(x,y);
ll d = deep[x]-deep[y];
for (ll i=0;i<=28;i++)
if (d&(1<<i)) x = fa[x][i];
for (ll i=28;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x = fa[x][i],y = fa[y][i];
if (x==y) return x;
else return fa[x][0];
}
ll get(ll x){return f[x]==x?x:f[x] = get(f[x]);}
int main(){
n = read();m = read();k = read();
for (ll i=1;i<=n;i++) g[i] = read();
for (int i=1;i<=n+m;i++) f[i] = i;
int tot = n;
for (ll i=1;i<=m;i++){
x = read();y = read();
int fx = get(x),fy = get(y);
used[fx] = used[fy] = 1;
Insert(++tot,fx);Insert(tot,fy);
f[fx] = tot;f[fy] = tot;
}
for (ll i=1;i<=k;i++) q[i].x = read(),q[i].y = read(),q[i].id = i;
for (ll i=1;i<=n+m;i++) if (!used[i]) deep[i] = 1,dfs(i,-1);
for (ll i=1;i<=k;i++){
ll fx = get(q[i].x),fy = get(q[i].y);
if (fx!=fy) {q[i].ans = 0;continue;}
else q[i].ans = deep[lca(q[i].x,q[i].y)];
}
sort(q+1,q+1+k,cmp);
for (ll i=1;i<=k;i++)
if (q[i].ans!=0){
if (g[q[i].x]<=g[q[i].y]){sum+=2ll*g[q[i].x];g[q[i].y]-=g[q[i].x];g[q[i].x] = 0;}
else {sum+=2ll*g[q[i].y];g[q[i].x]-=g[q[i].y];g[q[i].y] = 0;}
}
printf("%lld",sum);
}
评论 (0)
