Submission #98952

#	Time	Username	Problem	Language	Result	Execution time	Memory
98952		kjain_1810	Shell (info1cup18_shell)	C++17	75 / 100	279 ms	12664 KiB

shell

// #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=1505;
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 (stderr)

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 / 10
• Subtask 2: 45 / 45
• Subtask 3: 20 / 20
• Subtask 4: 0 / 25