Ранг хакера Подобные пары

Question

Я пытаюсь решить ранжирование хакеров аналогичные пары https://www.hackerrank.com/contests/101hack/challenges/similarpair проблема. Я не могу понять, почему он не подходит для больших тестовых случаев. Я использую деревья сегментов для решения этой проблемы в nlogn time. Вы можете найти мой код ниже.

#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-битный int.

Это получает 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; 

}