ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1471. Distance in the Tree

Crash (access violation) on test 1
Posted by Abzal 22 Aug 2011 23:46
plz, help me! why i get crash(access violation).
// LCA (least common ancestor) offline by using interval tree in O(logN)
// Solution by Serekov Abzal

#pragma comment(linker, "/STACK:16777216")

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

using namespace std;
int ADD = 65536;
int inf = 9999999;
vector <vector <pair<int, int> > > graph;
vector <bool> b(50001, false);
vector <int> h(50001, 0);
vector <int> order;
vector <int> d(50001, 0);
vector <int> first(50001, -1);
pair <int, int> tree[2 * 65536 + 1];
int n, root = 0;
void init_graph()
{
    scanf("%d", &n);
    graph.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
};
void dfs(int v, int p)
{
    b[v] = true;
    h[v] = p;
    order.push_back(v);
    for (int i = 0; i < graph[v].size(); i++)
        if (!b[graph[v][i].first])
        {
            dfs(graph[v][i].first, p + 1);
            order.push_back(v);
        }
};
void bfs(int v)
{
    queue <int> Q;
    Q.push(v);
    while (!Q.empty())
    {
        int u = Q.front();
        b[u] = true;
        for (int i = 0; i < graph[u].size(); i++)
            if (!b[graph[u][i].first])
            {
                d[graph[u][i].first] = d[u] + graph[u][i].second;
                Q.push(graph[u][i].first);
            }
        Q.pop();
    }
};
void prepare()
{
    h[root] = 0;
    dfs(root, 0);
    for (int i = 0; i < order.size(); i++)
        if (first[order[i]] == -1)
            first[order[i]] = i;
    for (int i = 0; i < n; i++) b[i] = false;
    d[root] = 0;
    bfs(root);
};
int minimum(int u, int v)
{
    int l = u, r = v, ans = inf, ver = inf;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            if (tree[l].second < ans)
            {
                ans = tree[l].second;
                ver = tree[l].first;
            }
            l++;
        };
        if (r % 2 == 0)
        {
            if (tree[r].second < ans)
            {
                ans = tree[r].second;
                ver = tree[r].first;
            }
            --r;
        }
        l/=2; r/=2;
    }
    return ver;
};
int lca(int u, int v)
{
    int l = first[u] + ADD, r = first[v] + ADD;
    return minimum(l, r);
};
void init_zaprosi()
{
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int ans = d[u] + d[v] - 2 * d[lca(u, v)];
        printf("%d\n", ans);
    }
};
void tree_build()
{
    for (int i = 0; i <= 2 * ADD; i++)
    tree[i] = make_pair(-1, inf);

    for (int i = ADD; i < ADD + order.size(); i++)
    {
        tree[i].first = order[i - ADD];
        tree[i].second = h[order[i - ADD]];
    }
    for (int i = ADD - 1; i > 0; i--)
    {
        if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1)
        {
            if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1))
            {
                if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i];
            }
        }
        else
        {
            if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i];    else tree[i] = tree[2 * i + 1];
        }
    }
};
int main()
{
    init_graph();
    prepare();
    tree_build();
    init_zaprosi();
    return 0;
}
Re: Crash (access violation) on test 1
Posted by Abzal 23 Aug 2011 15:28
I've just resized size of segment tree to 2 * 131072, and
one thing:

not everytime u < v, there can be like u > v, so i swaped them, and i got AC
Re: Crash (access violation) on test 1
Posted by Atiqur Rahman 28 Jul 2015 23:44
So, everyone assumed 0 is the root of the tree. I don't find it in the problem description.