[ZJ][LCA][offline] d767. 血緣關係＠Morris' Blog

2012-10-05 19:36:33| 人氣1,615| 回應0 | 上一篇 | 下一篇

[ZJ][LCA][offline] d767. 血緣關係

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

給一張祖譜,詢問 A , B 兩人關係最近的共同祖先以及 A , B 之間的親等
example 1

親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。

※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。

輸入說明：

第一行兩個數字 N , Q
分別代表接下來會有 N 行數字分別代表該人的兒女編號(以 0 表結束)，
再來會有 Q 行
每行上會有兩個數字 A , B ，代表要求出 A , B 兩人的關係最近的共同祖先
以及 A , B 之間的親等。
詳細請參考Sample Input。
(N≦3,0000, 1≦A,B≦N, Q≦N²)

輸出說明：

輸出兩個數字最近的共同祖先以及 A , B 之間的親等

範例輸入： help

範例輸出：

提示：

背景知識： RMQ

※　在此未符合實際事實，暫定一個人的兒女不超過6個

Ranged Minimum/Maximum Query(RMQ)
Least Common Ancestors (LCA)

出處：

RMQ & LCA (管理：morris1028)

學習文章 <- 請點閱

#include <stdio.h>
#include <vector>
#define maxN 32768
using namespace std;
typedef struct {
    int q, i;
} Qi;
vector<int> g[maxN];
vector<Qi> qu[maxN];
int r[maxN], p[maxN], dp[maxN], used[maxN];
int oput[500000][2];
int findp(int x) {
    return p[x] == x ? x : p[x]=findp(p[x]);
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    p[x] = y;
}
void dfs(int nd, int dep) {
    dp[nd] = dep, used[nd] = 1;
    for(vector<Qi>::iterator it = qu[nd].begin();
        it != qu[nd].end(); it++) {
        if(used[it->q]) {
            oput[it->i][0] = findp(it->q);
            oput[it->i][1] = dp[nd]+dp[it->q]-2*dp[findp(it->q)];
        }
    }
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        dfs(*it, dep+1);
        joint(*it, nd);
    }
}
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, q, x, y, i, j;
    while(scanf("%d %d", &n, &q) == 2) {
        for(i = 1; i <= n; i++) {
            g[i].clear(), r[i] = 1, p[i] = i, used[i] = 0;
            while(ReadInt(&x), x)
                g[i].push_back(x);
        }
        Qi tmp;
        for(i = 0; i < q; i++) {
            ReadInt(&x), ReadInt(&y);
            tmp.i = i, tmp.q = y;
            qu[x].push_back(tmp);
            tmp.q = x;
            qu[y].push_back(tmp);
        }
        dfs(1, 0);
        for(i = 0; i < q; i++)
            printf("%d %d\n", oput[i][0], oput[i][1]);
    }
    return 0;
}

我要檢舉

#d767#血緣關係

台長： Morris

您可能對以下文章有興趣

a135. 12250 - Language Detection

[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測

d807. 方方

[ZJ] a631. 11. LED Decoder

人氣(1,615) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ] a473. 外援計畫
此分類上一篇:[ZJ][LCA][online] d767. 血緣關係

回應(0)