2017暑期集训Day 8

T1:LCA

Code(倍增):

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MN 500005
#define L 20
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{ 
    int to,next; 
}e[MN];
queue<int>q;
int fa[MN][L+1],head[MN],dep[MN];
bool vis[MN];
int cnt=0,rt=0,n,qu,x,y;
inline void ins(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;}
inline void bfs(int x){
    vis[x]=1;q.push(x);
    while (!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if (!vis[v]) dep[v]=dep[u]+1,q.push(v);
        }
    }
}
inline void gf(){
    for (int j=1;j<=L;++j)
    for (int i=1;i<=n;++i) fa[i][j]=fa[fa[i][j-1]][j-1];
}
inline int lca(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);int dif=dep[u]-dep[v];
    for (int i=0;i<L;++i) if (dif&(1<<i)) u=fa[u][i];
    if (u==v) return u;for (int i=L-1;i>=0;--i)
    if (fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}
    u=fa[u][0];return u;
}
int main()
{
    n=in();qu=in();
    for (int i=1;i<n;++i){
        x=in();y=in();ins(x,y);fa[y][0]=x;
        if (!fa[x][0]) rt=x;
    }dep[rt]=1;bfs(rt);gf();
    for (int i=1;i<=qu;++i){x=in();y=in();printf("%d
",lca(x,y));}
    return 0;
}

 Code(Tarjan):

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Mx 500005
using namespace std; 
struct edge{int to,next;}e[1500005]; 
int h[Mx],q[Mx],f[Mx],a[Mx],cnt=0,n,m,c,b; 
bool r[Mx]; 
inline void ins(int *h,int x,int y){e[++cnt].to=y;e[cnt].next=h[x];h[x]=cnt;} 
inline int ff(int x){return f[x]?f[x]=ff(f[x]):x;} 
int tarjan(int u){ 
    for (int i=h[u];i;i=e[i].next){tarjan(e[i].to);f[e[i].to]=u;} 
    for (int i=q[u];i;i=e[i].next) 
    if(a[e[i].to]) a[e[i].to]=ff(a[e[i].to]); 
    else a[e[i].to]=u; 
      
} 
int main() 
{ 
    scanf("%d%d",&n,&m); 
    for(int i=1;i<n;i++){scanf("%d%d",&c,&b);ins(h,c,b);r[b]=1;} 
    for(int i=0;i<m;i++){scanf("%d%d",&c,&b);ins(q,c,i);ins(q,b,i);} 
    for(int i=1;i<=n;i++)if(!r[i]){tarjan(i);break;} 
    for(int i=0;i<m;i++)printf("%d
",a[i]); 
    return 0; 
}

 Code(树链剖分):

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Mx 500005
using namespace std; 
struct edge{int to,next;}e[1500005]; 
int h[Mx],q[Mx],f[Mx],a[Mx],cnt=0,n,m,c,b; 
bool r[Mx]; 
inline void ins(int *h,int x,int y){e[++cnt].to=y;e[cnt].next=h[x];h[x]=cnt;} 
inline int ff(int x){return f[x]?f[x]=ff(f[x]):x;} 
int tarjan(int u){ 
    for (int i=h[u];i;i=e[i].next){tarjan(e[i].to);f[e[i].to]=u;} 
    for (int i=q[u];i;i=e[i].next) 
    if(a[e[i].to]) a[e[i].to]=ff(a[e[i].to]); 
    else a[e[i].to]=u; 
      
} 
int main() 
{ 
    scanf("%d%d",&n,&m); 
    for(int i=1;i<n;i++){scanf("%d%d",&c,&b);ins(h,c,b);r[b]=1;} 
    for(int i=0;i<m;i++){scanf("%d%d",&c,&b);ins(q,c,i);ins(q,b,i);} 
    for(int i=1;i<=n;i++)if(!r[i]){tarjan(i);break;} 
    for(int i=0;i<m;i++)printf("%d
",a[i]); 
    return 0; 
}

T2:跳跳棋

Code:

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#define inf 1000000000 
using namespace std; 
inline int in(){ 
    int x=0;bool f=0; char c; 
    for (;(c=getchar())<'0'||c>'9';f=c=='-'); 
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 
    return f?-x:x; 
} 
struct hop{ 
    int p[3]; 
}a,b,r1,r2; 
inline bool operator !=(hop a,hop b){ 
    for (int i=0;i<3;++i) if (a.p[i]!=b.p[i]) return 1; 
    return 0; 
} 
int cnt=0,dep1,dep2,lca; 
inline hop gcd (hop x,int dep){ 
    hop ans; 
    int d1=x.p[1]-x.p[0],d2=x.p[2]-x.p[1]; 
    memcpy(ans.p,x.p,sizeof(x.p));if (d1==d2) return ans; 
    if (d1<d2){ 
        int d=min(dep,(d2-1)/d1); 
        dep-=d;cnt+=d;ans.p[1]+=d*d1;ans.p[0]+=d*d1; 
    }else{ 
        int d=min(dep,(d1-1)/d2); 
        dep-=d;cnt+=d;ans.p[2]-=d*d2;ans.p[1]-=d*d2; 
    }if (dep>0) return gcd(ans,dep);else return ans; 
} 
int main() 
{ 
    for (int i=0;i<3;++i) a.p[i]=in();sort(a.p,a.p+3); 
    for (int i=0;i<3;++i) b.p[i]=in();sort(b.p,b.p+3); 
    r1=gcd(a,inf);dep1=cnt;cnt=0;r2=gcd(b,inf);dep2=cnt;cnt=0; 
    if (r1!=r2) {printf("NO");return 0;} 
    if (dep1>dep2) {swap(dep1,dep2);for (int i=0;i<3;++i)swap(a.p[i],b.p[i]);} 
    int ct=dep2-dep1;b=gcd(b,ct);int l=0,r=dep1; 
    while (l<=r){ 
        int mid=(l+r)>>1; 
        if (gcd(a,mid)!=gcd(b,mid)) l=mid+1;else lca=mid,r=mid-1; 
    }printf("YES
%d",(lca<<1)+ct); 
    return 0; 
}

T3:树的统计

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define L (x<<1)
#define R (x<<1|1)
#define mid ((l+r)>>1)
#define inf 0x7fffffff
#define MN 30005
#define MM (1<<16)
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
inline int max(int a,int b){return a>b?a:b;}
struct edge{
    int to,next;
}e[MN<<1];
int head[MN],siz[MN],pos[MN],dep[MN],top[MN],son[MN],fa[MN];
int sum[MM],mx[MM],cnt=0,dfn=0,n,q,x,y,u,v,M;
char op[7];
inline void ins(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
inline void pre(int u){
    siz[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa[u]) continue;
        fa[v]=u;dep[v]=dep[u]+1;pre(v);siz[u]+=siz[v];
        if (siz[v]>siz[son[u]]) son[u]=v;
    }
}
inline void dfs(int u,int tp){
    top[u]=tp;pos[u]=(++dfn);if (son[u]) dfs(son[u],tp);
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v!=fa[u]&&v!=son[u]) dfs(v,v);
    }
}
inline void up(int x){
    sum[x]=sum[L]+sum[R];mx[x]=max(mx[L],mx[R]);
}
inline void update(int x,int v){
    x+=M;sum[x]=mx[x]=v;for (x>>=1;x;x>>=1) up(x);
}
inline int qmax(int l,int r){
    int ans=-inf;
    for (l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
        if (~l&1) ans=max(ans,mx[l^1]);
        if ( r&1) ans=max(ans,mx[r^1]);
    }return ans;
}
inline int qsum(int l,int r){
    int ans=0;
    for (l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
        if (~l&1) ans+=sum[l^1];
        if ( r&1) ans+=sum[r^1];
    }return ans;
}
inline int querym(int x,int y){
    int ans=-inf;
    while (top[x]!=top[y]){
        if (dep[top[x]]>dep[top[y]]) ans=max(ans,qmax(pos[top[x]],pos[x])),x=fa[top[x]];
        else ans=max(ans,qmax(pos[top[y]],pos[y])),y=fa[top[y]];
    }if (dep[x]<dep[y]) ans=max(ans,qmax(pos[x],pos[y]));
    else ans=max(ans,qmax(pos[y],pos[x]));return ans;
}
inline int querys(int x,int y){
    int ans=0;
    while (top[x]!=top[y]){
        if (dep[top[x]]>dep[top[y]]) ans+=qsum(pos[top[x]],pos[x]),x=fa[top[x]];
        else ans+=qsum(pos[top[y]],pos[y]),y=fa[top[y]];
    }if (dep[x]<dep[y]) ans+=qsum(pos[x],pos[y]);
    else ans+=qsum(pos[y],pos[x]);return ans;
}
int main()
{
    n=in();for (M=1;M<n+2;M<<=1);
    for (int i=1;i<n;++i){
        x=in();y=in();ins(x,y);ins(y,x);
    }fa[1]=1;dep[1]=1;pre(1);dfs(1,1);
    for (int i=1;i<=n;++i) sum[M+pos[i]]=mx[M+pos[i]]=in();
    for (int i=M-1;i;--i) up(i);q=in();
    for (int i=1;i<=q;++i){
        scanf("%s",op);u=in();v=in();
        if (op[1]=='H') update(pos[u],v);
        else if (op[1]=='M') printf("%d
",querym(u,v));
        else if (op[1]=='S') printf("%d
",querys(u,v));
    }return 0;
}

T4:货车运输

Code:

#include<iostream>   
#include<cmath>   
#include<cstdio>   
#include<cstdlib>   
#include<cstring>   
#include<vector>   
#include<queue>   
#include<algorithm>  
#define inf 0x7fffffff  
using namespace std;  
int fa[18][10005],dep[10005],dis[18][10005],head[10005],f[10005];  
int n,m,q,x,y,l,cnt,cur;  
bool vis[10005];  
const int maxpow=16;  
struct edge{int to,next,val;}e[20005];  
struct edg{int a,b,v;}ed[50005];  
bool cmp(edg a,edg b){return a.v>b.v;}  
void ins(int x,int y,int v)  
{e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].val=v;}  
int ff(int x){return f[x]==x?x:f[x]=ff(f[x]);}  
void kruskal()  
{  
    sort(ed+1,ed+m+1,cmp);  
    for (int i=1;i<=m;i++){  
        edg eg=ed[i];int af=ff(eg.a),bf=ff(eg.b);  
        if (af!=bf){  
            f[af]=bf;ins(eg.a,eg.b,eg.v);ins(eg.b,eg.a,eg.v);  
            cur++;if (cur==n-1) break;  
        }  
    }  
}  
void dfs(int u)  
{  
    vis[u]=true;  
    for (int i=1;i<=maxpow;i++)  
    {  
        if (dep[u]<(1<<i)) break;fa[i][u]=fa[i-1][fa[i-1][u]];  
        dis[i][u]=min(dis[i-1][u],dis[i-1][fa[i-1][u]]);  
    }  
    for (int i=head[u];i;i=e[i].next)  
    {  
        int v=e[i].to;  
        if (vis[v]) continue;  
        dep[v]=dep[u]+1;dis[0][v]=e[i].val;  
        fa[0][v]=u;dfs(v);  
    }  
}  
int lca(int u,int v)  
{  
    if (dep[u]<dep[v]) swap(u,v);  
    int dif=dep[u]-dep[v];  
    for (int i=0;i<=maxpow;i++) if ((1<<i)&dif) u=fa[i][u];  
    for (int i=maxpow;i>=0;i--)  
    if (fa[i][u]!=fa[i][v]) {u=fa[i][u];v=fa[i][v];}  
    if (u==v) return u;  
    return fa[0][u];  
}  
int fmn(int a,int b)  
{  
    int mn=inf,diff=dep[a]-dep[b];  
    for (int i=0;i<=maxpow;i++)  
    if (diff&(1<<i)){mn=min(mn,dis[i][a]);a=fa[i][a];}return mn;  
}  
int main()  
{  
    scanf("%d%d",&n,&m);  
    memset(dis,127/3,sizeof(dis));for (int i=1;i<=n;i++) f[i]=i;  
    for(int i=1;i<=m;i++)  
    scanf("%d%d%d",&ed[i].a,&ed[i].b,&ed[i].v);kruskal();  
    for (int i=1;i<=n;i++) if (!vis[i])dfs(i);scanf("%d",&q);  
    for (int i=1;i<=q;i++)  
    {  
        scanf("%d%d",&x,&y);  
        if (ff(x)!=ff(y)) {printf("-1
");continue;}  
        int anc=lca(x,y);  
        printf("%d
",min(fmn(x,anc),fmn(y,anc)));  
    }  
    return 0;  
}

T5:软件包管理器

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define L (x<<1)
#define R (x<<1|1)
#define mid ((l+r)>>1)
#define MN 100005
#define MM (1<<18)
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{ 
    int to,next; 
}e[MN]; 
int lazy[MM],sum[MM]; 
int fa[MN],siz[MN],dep[MN],son[MN],head[MN],top[MN],rps[MN],pos[MN]; 
int n,q,x,cnt=0,dfn=0; 
char op[10]; 
inline void ins(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
inline void pre(int u){
    siz[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        dep[v]=dep[u]+1;pre(v);siz[u]+=siz[v];
        if (son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
    }
}
inline void dfs(int u,int tp){
    top[u]=tp;pos[u]=(++dfn);if (son[u]!=-1) dfs(son[u],tp);
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;if (v!=son[u]) dfs(v,v);
    }rps[u]=dfn;
}
inline void up(int x){sum[x]=sum[L]+sum[R];}
inline void pushdown(int x,int l,int r){
    if (l==r||lazy[x]==-1) return;int M=r-l+1;
    sum[L]=(M-(M>>1))*lazy[x];sum[R]=(M>>1)*lazy[x];
    lazy[L]=lazy[R]=lazy[x];lazy[x]=-1;
}
inline void update(int x,int l,int r,int a,int b,int v){
    if (a<=l&&b>=r){int M=r-l+1;lazy[x]=v;sum[x]=M*v;return;}pushdown(x,l,r);
    if (a<=mid) update(L,l,mid,a,b,v);if (b>mid) update(R,mid+1,r,a,b,v);up(x);
}
inline int query(int x,int l,int r,int a,int b){
    if (a==l&&b==r) return sum[x];pushdown(x,l,r);
    if (b<=mid) return query(L,l,mid,a,b);if (a>mid) return query(R,mid+1,r,a,b);
    return query(L,l,mid,a,mid)+query(R,mid+1,r,mid+1,b);
}
inline int inst(int x){
    int ans=0;while (top[x]){
        ans+=pos[x]-pos[top[x]]+1-query(1,1,n,pos[top[x]],pos[x]);
        update(1,1,n,pos[top[x]],pos[x],1);x=fa[top[x]];
    }ans+=pos[x]-query(1,1,n,1,pos[x]);update(1,1,n,1,pos[x],1);return ans;
}
inline int unin(int x){
    int ans=0;ans=query(1,1,n,pos[x],rps[x]);
    update(1,1,n,pos[x],rps[x],0);return ans;
}
int main()
{
    n=in();memset(son,-1,sizeof(son));
    for (int i=1;i<n;++i) fa[i]=in(),ins(fa[i],i);
    fa[0]=0;dep[0]=1;pre(0);dfs(0,0);q=in();
    for (int i=1;i<=q;++i){
        scanf("%s",op);x=in();
        if (op[0]=='i') printf("%d
",inst(x));
        if (op[0]=='u') printf("%d
",unin(x));
    }return 0;
}