oj.uz

Submission #98953

# Submission time Handle Problem Language Result Execution time Memory
98953 2019-02-27T17:27:24 Z kjain_1810 Shell (info1cup18_shell) C++17
100 / 100
 525 ms 56968 KB 
// #include <bits/stdc++.h>
#include<cstdio>
#include<vector>
#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=1e6+5;
const int MOD=1e9+7;

typedef long long ll;
// typedef long double ld;

ll n, m, p, tovis[N], visord[N];
vector<ll>adj[N];
ll vis[N], nex[N], dp[N];

void dfs(ll u)
{
    vis[u]=1;
    if(visord[u]>0)
        nex[u]=visord[u];
    else
        nex[u]=MOD;
    for(ll a=0; a<adj[u].size(); a++)
    {
        ll v=adj[u][a];
        if(!vis[v])
            dfs(v);
        nex[u]=min(nex[u], nex[v]);
    }
}

void dfs2(ll u)
{
    vis[u]=1;
    if(u==tovis[p])
    {
        dp[u]=1;
        return;
    }
    ll chk=(nex[u]==u?tovis[visord[u]+1]:nex[u]);
    for(ll a=0; a<adj[u].size(); a++)
    {
        ll v=adj[u][a];
        if(!vis[v])
            dfs2(v);
        if(nex[v]==chk)
            dp[u]=(dp[u]+dp[v])%MOD;
    }
    // printf("%lld %lld\n", u, dp[u]);
}

int main() 
{
    inlld3(n, m, p);
    for(ll a=1; a<=p; a++)
        inlld(tovis[a]);
    if(tovis[1]!=1)
    {
        for(ll a=p+1; a>=2; a--)
            tovis[a]=tovis[a-1];
        tovis[1]=1;
        p++;
    }
    if(tovis[p]!=n)
        tovis[++p]=n;
    for(ll a=1; a<=p; a++)
        visord[tovis[a]]=a;
    while(m--)
    {
        ll u, v;
        inlld2(u, v);
        adj[u].pb(v);
    }
    for(ll a=1; a<=n; a++)
        if(!vis[a])
            dfs(a);
    for(ll a=1; a<=n; a++)
    {
        vis[a]=0;
        if(nex[a]<MOD)
            nex[a]=tovis[nex[a]];
    }
    for(ll a=1; a<=n; a++)
        if(!vis[a])
            dfs2(a);
    printf("%lld\n", dp[1]);
    return 0;
}

Compilation message

shell.cpp: In function 'void dfs(ll)':
shell.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll a=0; a<adj[u].size(); a++)
                 ~^~~~~~~~~~~~~~
shell.cpp: In function 'void dfs2(ll)':
shell.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll a=0; a<adj[u].size(); a++)
                 ~^~~~~~~~~~~~~~
shell.cpp: In function 'int main()':
shell.cpp:12: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:64:5: note: in expansion of macro 'inlld3'
     inlld3(n, m, p);
     ^~~~~~
shell.cpp:8: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:66:9: note: in expansion of macro 'inlld'
         inlld(tovis[a]);
         ^~~~~
shell.cpp:10: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:81:9: note: in expansion of macro 'inlld2'
         inlld2(u, v);
         ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23776 KB Output is correct
2 Correct 23 ms 23912 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 28 ms 23808 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23776 KB Output is correct
2 Correct 23 ms 23912 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 28 ms 23808 KB Output is correct
6 Correct 27 ms 23900 KB Output is correct
7 Correct 28 ms 24208 KB Output is correct
8 Correct 25 ms 24064 KB Output is correct
9 Correct 32 ms 24320 KB Output is correct
10 Correct 31 ms 24132 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23900 KB Output is correct
2 Correct 117 ms 29228 KB Output is correct
3 Correct 127 ms 29312 KB Output is correct
4 Correct 110 ms 29144 KB Output is correct
5 Correct 87 ms 27652 KB Output is correct
6 Correct 248 ms 35960 KB Output is correct
7 Correct 231 ms 36088 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23776 KB Output is correct
2 Correct 23 ms 23912 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 28 ms 23808 KB Output is correct
6 Correct 27 ms 23900 KB Output is correct
7 Correct 28 ms 24208 KB Output is correct
8 Correct 25 ms 24064 KB Output is correct
9 Correct 32 ms 24320 KB Output is correct
10 Correct 31 ms 24132 KB Output is correct
11 Correct 24 ms 23900 KB Output is correct
12 Correct 117 ms 29228 KB Output is correct
13 Correct 127 ms 29312 KB Output is correct
14 Correct 110 ms 29144 KB Output is correct
15 Correct 87 ms 27652 KB Output is correct
16 Correct 248 ms 35960 KB Output is correct
17 Correct 231 ms 36088 KB Output is correct
18 Correct 525 ms 56968 KB Output is correct
19 Correct 501 ms 54792 KB Output is correct
20 Correct 520 ms 51928 KB Output is correct
21 Correct 177 ms 35008 KB Output is correct
22 Correct 495 ms 54136 KB Output is correct