USACO 2012 Gold December Contest: "Running Away From the Barn" Solution Almost Identical to the Judge's Fails

Revision en1, by vamaddur, 2017-07-04 20:30:23

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213

My code below is my attempt to solve this problem, which keeps failing cases 7 through 9. I do not see a significant difference between my logic and the logic of the judge solution (the last one in the editorial here Your text to link here...). Can someone explain why my solution keeps producing a WA? I even resorted to changing my code to 0 based indexing after 3 hours of trying to perfectly match the judge solution, with no change in output. I sincerely apologize for posting a wall of code, but I have not found another way to resolve the issue after privately asking other users to look over it for me.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int id = 1;

struct Node{
    Node *parent;
    vector<Node*> children;
    long long depth;
    int last, label;
    Node(){ parent = NULL; depth = 0ll; last = -1; }
    void preorder(){
        label = id++;
        for(int i = 0; i < children.size(); i++) children[i]->preorder();
        if(children.size() == 0) last = label;
        else last = children.back()->last;
    }
};

struct Event{
    int a, b, index;
    long long len;
    bool operator<(const Event &other) const{
        if(len != other.len) return len < other.len;
        else return a < other.a;
    }
};

int N;
Node tree [400001];
long long L, fenwick [400001], ret [400001];
vector<Event> events;

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

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

int main(){
    freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);
    scanf("%d %d", &N, &L);
    for(int i = 2; i <= N; i++){
        int x; long long y; scanf("%d %lld", &x, &y);
        Node *par = tree+x;
        tree[i].parent = par;
        tree[i].depth = (par->depth)+y;
        par->children.push_back(tree+i);
    }
    tree[1].preorder();
    for(int i = 1; i <= N; i++){
        Event c;
        c.a = -1; c.b = -1;
        c.len = tree[i].depth; c.index = tree[i].label;
        Event d;
        d.a = tree[i].label; d.b = tree[i].last;
        d.len = tree[i].depth+L; d.index = i;
        events.push_back(c); events.push_back(d);
    }
    sort(events.begin(), events.end());
    for(int i = 0; i < events.size(); i++){
        Event e = events[i];
        if(e.a == -1) add(e.index, 1ll);
        else ret[e.index] = query(e.b)-query(e.a-1);
    }
    for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
    return 0;
}

Please help, and thanks in advance!

Tags usaco, bit/fenwick tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vamaddur 2017-07-04 20:30:23 3006 Initial revision (published)