oj.uz

Submission #93807

# Submission time Handle Problem Language Result Execution time Memory
93807 2019-01-11T13:31:14 Z kjain_1810 Shell (info1cup18_shell) C++17
55 / 100
 1000 ms 17916 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define ind2(a, b) scanf("%d%d", &a, &b)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

using namespace std;

const int N=1e3+5;
const int MOD=1e9+7;

typedef long long ll;
typedef long double ld;

ll n, m, p, arr[N], dp[N][N];
vector<ll>adj[N];

ll solve(ll i, ll j)
{
    if(i==n)
        return j==p;
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll ret=0;
    for(ll a=0; a<adj[i].size(); a++)
    {
        ll v=adj[i][a];
        if(v==arr[j+1])
            ret=(ret+solve(v, j+1))%MOD;
        else
            ret=(ret+solve(v, j))%MOD;
    }
    return dp[i][j]=ret;
}

int main() 
{
    inlld3(n, m, p);
    for(ll a=1; a<=p; a++)
    {
        inlld(arr[a]);
        if(a!=p && arr[a]==n)
        {
            printf("0\n");
            return 0;
        }
    }
    while(m--)
    {
        ll u, v;
        inlld2(u, v);
        adj[u].pb(v);
    }
    memset(dp, -1, sizeof(dp));
    if(arr[1]!=1)
        printf("%lld\n", solve(1, 0));
    else
        printf("%lld\n", solve(1, 1));
    return 0;
}

Compilation message

shell.cpp: In function 'll solve(ll, ll)':
shell.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll a=0; a<adj[i].size(); a++)
                 ~^~~~~~~~~~~~~~
shell.cpp: In function 'int main()':
shell.cpp:10:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:43:5: note: in expansion of macro 'inlld3'
     inlld3(n, m, p);
     ^~~~~~
shell.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld(a) scanf("%lld", &a)
                  ~~~~~^~~~~~~~~~~~
shell.cpp:46:9: note: in expansion of macro 'inlld'
         inlld(arr[a]);
         ^~~~~
shell.cpp:8:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define inlld2(a, b) scanf("%lld%lld", &a, &b)
                      ~~~~~^~~~~~~~~~~~~~~~~~~~
shell.cpp:56:9: note: in expansion of macro 'inlld2'
         inlld2(u, v);
         ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 8 ms 8312 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 7 ms 8312 KB Output is correct
5 Correct 9 ms 8188 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 8 ms 8312 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 7 ms 8312 KB Output is correct
5 Correct 9 ms 8188 KB Output is correct
6 Correct 8 ms 8312 KB Output is correct
7 Correct 49 ms 8568 KB Output is correct
8 Correct 37 ms 8532 KB Output is correct
9 Correct 16 ms 8952 KB Output is correct
10 Correct 22 ms 8824 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8312 KB Output is correct
2 Execution timed out 1071 ms 17916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 8 ms 8312 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 7 ms 8312 KB Output is correct
5 Correct 9 ms 8188 KB Output is correct
6 Correct 8 ms 8312 KB Output is correct
7 Correct 49 ms 8568 KB Output is correct
8 Correct 37 ms 8532 KB Output is correct
9 Correct 16 ms 8952 KB Output is correct
10 Correct 22 ms 8824 KB Output is correct
11 Correct 10 ms 8312 KB Output is correct
12 Execution timed out 1071 ms 17916 KB Time limit exceeded
13 Halted 0 ms 0 KB -