Submission #97931

#	Time	Username	Problem	Language	Result	Execution time	Memory
97931		314rate	Shell (info1cup18_shell)	C++14	100 / 100	526 ms	48204 KiB

shell

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MOD=(int)1e9+7;

int add(int a,int b)
{
        a+=b;
        if(a>=MOD)
        {
                a-=MOD;
        }
        if(a<0)
        {
                a+=MOD;
        }
        return a;
}

int mul(int a,int b)
{
        return a*(long long)b%MOD;
}

const int N=(int)1e6+7;

int n;
int m;
int p;

int a[N];
int id[N];

vector<int>g[N];

int dp[N];
bool viz[N];

int nxt[N];

void build(int nod)
{
        viz[nod]=1;
        if(id[nod]>0)
        {
                nxt[nod]=id[nod];
        }
        else
        {
                nxt[nod]=(1<<30);
        }
        for(auto &nou:g[nod])
        {
                if(viz[nou]==0) build(nou);
                nxt[nod]=min(nxt[nod],nxt[nou]);
        }
}

void calc(int nod)
{
        viz[nod]=1;
        if(nod==a[p])
        {
                dp[nod]=1;
                return;
        }
        int urm;
        if(nxt[nod]==nod)
        {
            ///    cout<<"("<<nod<<" , "<<id[nod]+1<<")\n";
                urm=a[id[nod]+1];
        }
        else
        {
                urm=nxt[nod];
        }
    ///    cout<<nod<<" -> "<<urm<<"\n";
        for(auto &nou:g[nod])
        {
                if(viz[nou]==0) calc(nou);
                if(nxt[nou]!=urm) continue;
                dp[nod]=add(dp[nod],dp[nou]);
        }
}

void del(int id)
{
        for(int i=id;i<p;i++)
        {
                a[i]=a[i+1];
        }
        p--;
}

void rep()
{
        if(p>=2 && a[1]==a[2])
        {
                del(1);
        }
        if(p>=2 && a[p-1]==a[p])
        {
                del(a[p]);
        }
}

int main()
{
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      ///  freopen("input","r",stdin);
      ///  freopen("output","w",stdout);
        cin>>n>>m>>p;
        a[1]=1;
        for(int i=2;i<=p+1;i++)
        {
                cin>>a[i];
        }
        p+=2;
        a[p]=n;
        rep();
        for(int i=1;i<=n;i++)
        {
                id[a[i]]=i;
        }
        for(int i=1;i<=m;i++)
        {
                int x,y;
                cin>>x>>y;
                g[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
        {
                if(viz[i]==0)
                {
                        build(i);
                }
        }
        for(int i=1;i<=n;i++)
        {
                viz[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
                if(nxt[i]!=(1<<30))
                {
                        nxt[i]=a[nxt[i]];
                }
        }
        for(int i=1;i<=n;i++)
        {
                if(viz[i]==0)
                {
                        calc(i);
                }
        }
        cout<<dp[1]<<"\n";
        return 0;

        for(int i=1;i<=n;i++)
        {
                cout<<i<<" -> "<<dp[i]<<"\n";
        }

        return 0;
        dp[1]=add(dp[1],-1);
        cout<<dp[1]<<"\n";
        return 0;

        for(int i=1;i<=n;i++)
        {
                cout<<"\t\t"<<i<<" => "<<dp[i]<<"\n";
        }

        return 0;
        /**cout<<": ";
        for(int i=1;i<=p;i++)
        {
                cout<<a[i]<<" ";
        }
        cout<<"\n";**/
        for(int i=1;i<=n;i++)
        {
                cout<<i<<" => "<<nxt[i]<<"\n";
        }
        return 0;
}
/**

**/

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25