z-sumpaths

Hi, it's me again :)

This time the problem is TLE ( 23/25 OK , 2/25 TLE )
Well basically my idea is:
DP[<node>][<sum-needed-from-here>]
The trivial case of "parent->current_node->some_child.." is OK but the case of "child->current_node->child" runs too slow ;(
At first my DP was recursive but I decided to to do it iteratively, so I now have both versions ( iterative is done with toposort first, everything is OK with it too )... I don't know the tests ( does anyone know how to find them ? ) nor can I think of some optimisation... Here is my code ( it's a bit long ... sorry for that, concentrate on calc() )

/*
PROB: zsumpaths
LANG: C++
*/
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cstring>
#include <queue>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define foreach(_var,_container) for( typeof( (_container).begin() ) _var = (_container).begin() ; _var != (_container).end() ; ++_var )
#define now() double( double( clock() ) / double( CLOCKS_PER_SEC ) )
#if 0
#define eprintf(msg, ... ) fprintf(stderr," %s:%d in %s at %.4lf :: " msg "\xA" , strrchr( __FILE__ , '/' )+1 , __LINE__ , __FUNCTION__ , now() , ##__VA_ARGS__ )
#else
#define eprintf(msg, ... ) 0
#endif
#define pprintf(msg, ... ) fprintf(stderr," %s:%d in %s at %.4lf :: " msg "\xA" , strrchr( __FILE__ , '/' )+1 , __LINE__ , __FUNCTION__ , now() , ##__VA_ARGS__ )

using namespace std;

template< class T >
inline void remax( T &a , T b){
	a = max( a , b );
}

template< class T >
inline void remin( T &a , T b ){
	a = min( a , b );
}

const int MAXN = 50003;
const int MAXM = 101;
const int MOD = 321555123;

struct Edge{
    int cost;
    int destination;
    
    Edge(){}
    Edge( int destination , int cost ){
        this->destination = destination;
        this->cost = cost;
    }
    
    inline bool operator<( const struct Edge& other ) const{
        return cost < other.cost;
    }
};

int N,M;

int len;
int sorted[MAXN];/// topological sort
int sizes[MAXN];

vector< struct Edge > e[MAXN];

struct MyVector{
    /**
     * TLE with STL vector<>... trying to do it with myvector implementantion
     *  with static type
     */
    unsigned _size;
    unsigned reserved;
    struct Edge *list;
    
    MyVector(){
        list = NULL;
        _size = 0;
        reserved = 0;
    }
    
    void reserve( int to_which ){
        if( list == NULL ){
            reserved = ( to_which ? to_which : 10 );
            list = new struct Edge[reserved];
        }else{
            reserved = to_which;
            struct Edge *newlist = new struct Edge[reserved];
            
            for( int i = 0 ; i < _size ; i++ )
                newlist[i] = list[i];
            delete list;
            
            list = newlist;
        }
    }
    
    inline void push_back( struct Edge& new_element ){
        if( _size == reserved )
            reserve( reserved << 1 );
        
        list[_size++] = new_element;
    }
    
    inline int size() const{
        return this->_size;
    }
    
    inline struct Edge& operator[]( int index ) const{
        return list[index];
    }
};

struct MyVector e2[MAXN];

unsigned dp[MAXN][MAXM];

void toMyVector(){
    for( int i = 0 ; i < N ; i++ ){
        e2[i].reserve( sizes[i] );
        
        for( int j = 0 ; j < sizes[i] ; j++ )
            e2[i].push_back( e[i][j] );
    }
}

void toposort( int vertex , int parent ){
    vector< struct Edge >::iterator parentloc = e[vertex].end();
    
    foreach( child , e[vertex] ){
        if( child->destination == parent ){
            parentloc = child;
            continue;
        }
        toposort( child->destination , vertex );
    }
    if( parentloc != e[vertex].end() )
        e[vertex].erase( parentloc );
    
    sorted[len++] = vertex;
}

void calc(){
    for( int node_idx = 0 ; node_idx < N ; node_idx++ ){
        int node = sorted[ node_idx ];
        
        eprintf("At Node #%d with %d ch.", node, sizes[node] );
        
        /**
         * Always possible to get 0 in 1 way
         */
        
        dp[node][0] = 1;
        
        /**
         * Leafs are dead end...
         */
        
        if( sizes[node] == 0 )
            continue;
        
        /**
         * Regular paths Parent->Current->Child
         */
        
        for( int need = 0 ; need <= M ; need++ ){
            for( int i = 0 ; i < sizes[node] ; i++ ){
                struct Edge *child = &e2[node][i];
                if( child->cost > need )
                    break;
                
                dp[ node ][ need ] += dp[ child->destination ][ need - child->cost ];
            }
            
            dp[ node ][ need ] %= MOD;
        }
        
        /**
         * Unregulard path Child->Current->Child
         */
        
        for( register int i = 0 ; i < sizes[node] - 1 ; i++ ){
            
            for( int need = M ; need >= e2[node][i].cost ; need-- ){
                if( dp[ e2[node][i].destination ][ need - e2[node][i].cost ] == 0 )
                    continue;
                
                for( int j = i+1 ; j < sizes[node] and e2[node][j].cost <= M - need ; j++ ){
                    
                    dp[ node ][ M ] += dp[ e2[node][i].destination ][ need - e2[node][i].cost ] *
                        dp[ e2[node][j].destination ][ M - need - e2[node][j].cost ];
                }
                
                dp[ node ][ M ] %= MOD;
            }
        }
    }
}

int main( int argc, char* argv[] ){
	//freopen("zsumpaths.in" , "r" , stdin );
	//freopen("zsumpaths.out" , "w" , stdout );

    scanf("%d %d", &N, &M);
    
    for( int i = 0 ; i < N-1 ; i++ ){
        int a,b,w;
        
        scanf("%d %d %d", &a, &b, &w);
        
        --a, --b;
        
        e[a].push_back( Edge( b , w ) );
        e[b].push_back( Edge( a , w ) );
    }
    
    toposort( 0 , -1 );
    
    for( int i = 0 ; i < N ; i++ ){
        sizes[i] = e[i].size();
        
        sort( e[i].begin() , e[i].end() );
    }
    
    toMyVector();
    
    calc();
    
    unsigned result = 0;
    
    for( int i = 0 ; i < N ; i++ ){
        eprintf("From node %d it's %d", i, dp[i][M] );
        
        result = ( result + dp[i][M] % MOD ) % MOD;
    }
    
    eprintf("Answer is %d", result );
    
    printf("%u\n", result );

	fprintf( stderr , "Total runtime: %.4lf\xA", now() );
	return 0;
}

use this in your code, instead of scanf

int read_int () {
    static char c;
    static ll ret;
    while ( !isdigit ( c = read_char() ) );
    ret = c - '0';
    while ( isdigit ( c = read_char() ) ) {
          ret *= 10;
          ret += c - '0';
    }
    return ret;
}

then input is like this:

A = read_int();
B= read_int();
ect.

@matteo, u didn't declared read_char, and I think that fatulks solution fails because he has sorting of edges...

I think matteo meant that my input was slow.... other from that, the sorting is OK( how do you suppose going on tree dp iteratively ? )

Edit: the speeding input thing didn't quite do it.. still 2 TLs...

give me your email, i'll send you the test cases you need.

The dp idea is fine I guess, it can be implemented by having a simple depth-first traversal of the tree while calculating the values of the table along the way...
And also, no need for sorting of any kind in this problem.. seriously.

Well, the sorting is O(N) dfs to find a topological sort so that I can calculate DP[] iteratively... I have a recursive version with no sorting... it too gets TLE( in fact I tried recursive to iterative only because of the TLE )... So if I do it recursively, there is no sorting indeed :) Still too slow though ;(

sent

Could you calculate your complexity perhaps? I find the part with four nested loops a bit too complex to pass, and it seems to depend on the topology of the tree a lot. My worst case complexity is O( NM ).

The complexity is ... i don't wanna think about it :D It's hard to come up with an exact formula, maybe O(N^2 x M) which is really too slow but I just can't see how I can implement a O(NM) solution. Could you give me a hint?

Solved. I used a second DP to optimise to the inner cycle :) Thanks to all who had the patience and willingness to help me :)