Is my alternate approach to USACO 2012 Gold December Contest: "Running Away From the Barn" valid?
Difference between en1 and en2, changed 1,916 character(s)
Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213↵

For whatever reason, implementing any of the three official editorial solutions is not working out for me, so I am changing tact.↵

My idea is to store the depths relative to the root for each node, run a DFS and BIT similar to what I used in [this problem](http://mirror.codeforces.com/blog/entry/53060), add/subtract values to/from the BIT according to a sliding window (e.g. when L = 3 and a node with depth 5 is at the bottom of the sliding window, nodes with depth of at most 8 are at the top), and query all nodes in the window that are ancestors of the node in question.↵

I would appreciate comments on my method.↵

Please help, and thanks in advance!


UPD: I coded my fourth attempted solution, only for it to fail the same cases (7, 8, and 9). I would appreciate it if someone could find out what is wrong with it, as I have wasted 8+ hours trying to upsolve this problem to get no variance/change in results. ↵


~~~~~↵
#include <iostream>↵
#include <stdio.h>↵
#include <stdlib.h>↵
#include <algorithm>↵
#include <vector>↵
#include <unordered_set>↵

using namespace std;↵

int N;↵
vector<int> children [200001];↵
pair<long long, int> pis [200001];↵
int tree [200001], id [200001], mx [200001], ret [200001], curr = 1, index = 1;↵
long long L, depth [200001];↵

void add(int pos, long long x){↵
    while(pos < 200001){↵
        tree[pos] += x;↵
        pos += (pos&-pos);↵
    }↵
}↵

int query(int pos){↵
    int sum = 0;↵
    while(pos > 0){↵
        sum += tree[pos];↵
        pos -= (pos&-pos);↵
    }↵
    return sum;↵
}↵

int dfs(int x){↵
    id[x] = curr++; mx[x] = id[x];↵
    for(int i = 0; i < children[x].size(); i++){↵
        int next = children[x][i];↵
        mx[x] = max(mx[x], dfs(next));↵
    }↵
    return mx[x];↵
}↵

int main(){↵
    //freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);↵
    scanf("%d %d", &N, &L); depth[0] = 0ll;↵
    for(int i = 2; i <= N; i++){↵
        int x; long long y; scanf("%d %I64d", &x, &y);↵
        children[x].push_back(i); depth[i] = depth[x]+y;↵
    }↵
    dfs(1);↵
    for(int i = 1; i <= N; i++) pis[i] = make_pair(depth[i], i);↵
    sort(pis+1, pis+N+1);↵
    for(int i = 1; i <= N; i++){↵
        long long curDepth = pis[i].first; int now = pis[i].second; int from = id[now]; int to = mx[now];↵
        while(index <= N && curDepth+L >= depth[pis[index].second]){↵
            add(id[pis[index].second], 1);↵
            index++;↵
        }↵
        ret[now] = query(to)-query(from-1);↵
    }↵
    for(int i = 1; i <= N; i++) cout << ret[i] << '\n';↵
    return 0;↵
}↵
~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vamaddur 2017-07-05 16:04:44 1916
en1 English vamaddur 2017-07-04 23:20:41 822 Initial revision (published)