algorithm - 黑客排名相似对

Question

我正在尝试解决黑客等级相似对 https://www.hackerrank.com/contests/101hack/challenges/similarpair问题。我无法弄清楚为什么它在大型测试用例中失败。我正在使用线段树在 nlogn 时间内解决这个问题。您可以在下面找到我的代码。

#include<iostream>
#include<vector>

using namespace std;

vector<int> graph[110001];
int T, ST[100001*4] = {0}, N, deg[100001] = {0};

void update(int node, int b, int e, int idx, int val)  {

    if(b > node || e < node) return;

    if(b == e) {
        ST[idx] += val;
        return;
    }

    update(node, b, (b + e)/2, 2 * idx, val);
    update(node, (b + e)/2 + 1, e, 2 * idx + 1, val);

    ST[idx] = ST[2 * idx]  + ST[2 * idx + 1];

}

long Query(int l, int r, int b, int e, int idx) {

    if( l > e || r < b) return 0;

    if(l <= b && r >= e) return ST[idx];

    return Query(l, r, b, (b + e)/2, 2 * idx) + Query(l, r, (b + e)/2 + 1, e, 2 * idx + 1);
}

long long SimilarPairs(int node) {

    int l = max(1, node - T), r  = min(N, node + T);
    long res = 0;

    res = Query(l, r, 1, N, 1);

    update(node, 1, N, 1, 1);

    for(int i = 0; i < graph[node].size(); i++) {
       res +=  SimilarPairs(graph[node][i]);
    }

    update(node, 1, N, 1, -1);

    return res;
}

int main() {

    long x, y, root, result, start;


    cin >> N >> T;

    for(int i = 0; i < N - 1; i++) {
        cin >> x >> y;
        graph[x].push_back(y);
        deg[y]++;
    }

    for(int i = 1; i <= N; i++) if(!deg[i]) root = i;

    result = SimilarPairs(root);

    cout << result << endl;

    cin.get();

    return 0;

}

Answer 1

我明白你在做什么。问题是您缺少一些 long long。 long 与 int(在 32 位上)相同，因此您必须在任何地方使用 long long，因为结果不一定适合一个 32 位整数。

这得到 AC:

#include<iostream>
#include<vector>

using namespace std;

vector<int> graph[110001];
int T, N, deg[100001] = {0};
long long ST[100001*4] = {0};

void update(int node, int b, int e, int idx, int val)  {

    if(b > node || e < node) return;

    if(b == e) {
        ST[idx] += val;
        return;
    }

    int m = (b + e) >> 1;
    int q = idx << 1;
    update(node, b, m, q, val);
    update(node, m + 1, e, q + 1, val);

    ST[idx] = ST[q]  + ST[q+1];

}

long long Query(int l, int r, int b, int e, int idx) {

    if( l > e || r < b) return 0;

    if(l <= b && r >= e) return ST[idx];

    int m = (b + e) >> 1;
    int q = idx << 1;
    return Query(l, r, b, m, q) + Query(l, r, m + 1, e, q + 1);
}

long long SimilarPairs(int node) {

    int l = max(1, node - T), r  = min(N, node + T);
    long long res = 0;

    res = Query(l, r, 1, N, 1);

    update(node, 1, N, 1, 1);

    for(int i = 0; i < graph[node].size(); i++) {
       res +=  SimilarPairs(graph[node][i]);
    }

    update(node, 1, N, 1, -1);

    return res;
}

int main() {

    long x, y, root, start;


    cin >> N >> T;

    for(int i = 0; i < N - 1; i++) {
        cin >> x >> y;
        graph[x].push_back(y);
        deg[y]++;
    }

    for(int i = 1; i <= N; i++) if(!deg[i]) root = i;

    long long result = SimilarPairs(root);

    cout << result << endl;

    cin.get();

    return 0;

}