Submission #95563

#	Time	Username	Problem	Language	Result	Execution time	Memory
95563		oolimry	Journey (NOI18_journey)	C++14	100 / 100	253 ms	40008 KiB

journey

#include <bits/stdc++.h>

using namespace std;
typedef long long l;
typedef pair<l, l> ii;

///stores edges where it comes from, not goes to
vector<ii> adj[10005];
l e;
l memo[10005][405];
///isWaiting 0 - false, 1- true
l dp(l city, l nights){

    if(nights < 0){
        return 0;
    }
    if(city == 0 && nights == 0){
        return 1;
    }

    if(memo[city][nights] != -1){
        return memo[city][nights];
    }

    l ways = 0;


    for(l i = 0;i < adj[city].size();i++){
        l neigh = adj[city][i].first;
        l time = adj[city][i].second;

        if(neigh < city){
            ways += dp(neigh, nights - time);
        }

        if(ways > 500000001){
            return 500000001;
        }

    }
    if(city != e){
        ways += dp(city, nights - 1);
    }
    //printf("%d %d %d\n",city,nights,ways);
    if(ways > 500000001){
        return 500000001;
    }
    memo[city][nights] = ways;
    return ways;
}

int main()
{
    //freopen("i.txt","r",stdin);
    l n, m, h;
    scanf("%lld %lld %lld",&n,&m,&h);
    e = n - 1;
    for(int i = 0;i < n - 1;i++){
        for(int j = 0;j < h;j++){
            l a, b;
            scanf("%lld %lld", &a, &b);
            adj[a].push_back(ii(i,b));
        }
    }

    memo[0][0] = 1;
    for(int i = 0;i < 10003;i++){
        for(int j = 0 ;j < 403;j++){
            memo[i][j] = -1;
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < adj[i].size();j++){
            //printf("%lld %lld | ",adj[i][j].first,adj[i][j].second);
        }
        //printf("\n");
    }

    for(int i = 0;i < m;i++){
        printf("%lld ",dp(n-1, i));
        //printf("\n\n\n");
    }


    return 0;
}

Compilation message (stderr)

journey.cpp: In function 'l dp(l, l)':
journey.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(l i = 0;i < adj[city].size();i++){
                 ~~^~~~~~~~~~~~~~~~~~
journey.cpp: In function 'int main()':
journey.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < adj[i].size();j++){
                       ~~^~~~~~~~~~~~~~~
journey.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld",&n,&m,&h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
journey.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31