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, 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;
}
BUMP!
Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).
Can someone please help me on this?
Take a look at the C/C++ technical details on the instructions page (http://www.usaco.org/index.php?page=instructions).
It seems like it's just some issues with IO methods. First, you should change scanf("%d %d", &N, &L) to scanf("%d %lld", &N, &L), seems like you forgot that L was long long. Also, you should try to use the %lld flag isntead of %I64 for USACO, or at least that's what the specifications page says, not sure whether it actually changes anything. I tried submitting your solution after altering the items above. It works.
I'm not sure why the code above didn't have my %I64 in the first scanf, but changing it to lld surprisingly worked.
I say surprisingly because CodeForces does not allow C++ users to use "%lld" in place of "%I64" to make "safer" submissions.