BZOJ2791 Rendezvous

Description
给定一个n个顶点的有向图，每个顶点有且仅有一条出边。
对于顶点i，记它的出边为(i, a[i])。
再给出q组询问，每组询问由两个顶点a、b组成，要求输出满足下面条件的x、y：
1. 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。
2. 在满足条件1的情况下max(x,y)最小。
3. 在满足条件1和2的情况下min(x,y)最小。
4. 在满足条件1、2和3的情况下x>=y。
如果不存在满足条件1的x、y，输出-1 -1。
Input
第一行两个正整数n和q (n,q<=500,000)。
第二行n个正整数a[1],a[2],...,a[n] (a[i]<=n)。
下面q行，每行两个正整数a,b (a,b<=n)，表示一组询问。
Output
输出q行，每行两个整数。

思路：其实我觉得基环树题就是暴力模拟题……先找环，然后有多种情况，在环上某点的同一子树下，在环上不同子树下，不在同一联通块内，一一处理即可

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + ;

int head[N], now;

struct edges{

    int to, next, w;

}edge[N<<];

void add(int u, int v, int w){ edge[++now] = {v, head[u], w}; head[u] = now;}

void read(int &x){

    int f=;x=;char s=getchar();

    while(s<''||s>''){if(s=='-')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    x*=f;

}

int n, q, dfn[N], sz, pre[N], tot, c[N], dict[N], bel[N], fa[N][], dep[N], pos[N];

vector<int> cir[N];

void fcur(int x){

    dfn[x] = ++sz; bel[x] = tot;

    for(int i = head[x]; i; i = edge[i].next){

        int v = edge[i].to;

        if(v == pre[x]) continue;

        if(dfn[v]){

            if(dfn[v] < dfn[x]) continue;

            cir[tot].push_back(x); c[x] = tot;

            for(; x != v; v = pre[v]){

                cir[tot].push_back(v), c[v] = tot;

            }

        }else pre[v] = x, fcur(v);

    }

    return ;

}

void dfs(int x, int father, int root){

    dict[x] = root; fa[x][] = father;

    for(int i = head[x]; i; i = edge[i].next){

        int v = edge[i].to;

        if(v == father || c[v]) continue;

        dep[v] = dep[x] + ;

        dfs(v, x, root);

    }

}

int LCA(int u,int v){

    if(dep[u]<dep[v]) swap(u,v);

    int k=dep[u]-dep[v];

    for(int i=;i<=;i++)

      if((<<i)&k) u=fa[u][i];

    if(u==v) return u;

    for(int i=;i>=;i--)

      if(fa[u][i]!=fa[v][i])

        u=fa[u][i],v=fa[v][i];

    return fa[u][];

}

void dfs2(int x, int step){

    pos[x] = step;

    for(int i = head[x]; i; i = edge[i].next){

        int v = edge[i].to;

        if(edge[i].w && !pos[v]) dfs2(v, step + );

    }

}

int main(){

    read(n), read(q);

    int x, y;

    for(int i = ; i <= n; i++){

        read(x);

        add(i, x, ), add(x, i, );

    }

    for(int i = ; i <= n; i++){

        if(!dfn[i]){

            sz = ;  tot++;

            fcur(i);

        }

    }

    for(int i = ; i <= tot; i++){

        dfs2(cir[i][], );

        for(int j = ; j < cir[i].size(); j++){

            x = cir[i][j];

            dict[x] = x;

            dfs(x, x, x);

        }

    }

    for(int j = ; j <= ; j++)

      for(int i = ; i <= n; i++)

          fa[i][j + ] = fa[fa[i][j]][j];

    while(q--){

        scanf("%d%d", &x, &y);

        if(bel[x] != bel[y]){

            puts("-1 -1");  continue;

        }else if(dict[x] == dict[y]){

            int lca = LCA(x, y);

            printf("%d %d\n", dep[x] - dep[lca], dep[y] - dep[lca]);

        }else{

            int rt1 = dict[x], rt2 = dict[y], siz = cir[bel[x]].size();

            int s1 = dep[x] - dep[rt1], s2 = dep[y] - dep[rt2];

            int k1, k2;

            if(pos[rt1] < pos[rt2])  k1 = pos[rt2] - pos[rt1], k2 = siz - k1;

            else k2 = pos[rt1] - pos[rt2], k1 = siz - k2;

            int tmp1 = s1 + k1, tmp2 = s2 + k2;

            if(max(tmp1, s2) != max(s1, tmp2)){

                if(max(tmp1, s2) > max(s1, tmp2)) printf("%d %d\n", s1, tmp2);

                else printf("%d %d\n", tmp1, s2);

                continue;

            }

            else if(min(tmp1, s2) != min(s1, tmp2)){

                if(min(tmp1, s2) > min(s1, tmp2)) printf("%d %d\n", s1, tmp2);

                else printf("%d %d\n", tmp1, s2);

                continue;

            }

            else{

                if(tmp1 >= s2) printf("%d %d\n", tmp1, s2);

                else printf("%d %d\n", s1, tmp2);

            }

        }

    }

    return ;

}

巴特西

BZOJ2791 Rendezvous

最新文章

热门文章