Submission #489651

#	Time	Username	Problem	Language	Result	Execution time	Memory
489651		lucri	Shell (info1cup18_shell)	C++17	100 / 100	254 ms	33876 KiB

shell

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long p,n,m,c[1000010],st[1000010],nr,mua[1000010],x,y;
vector<vector<long long>>a;
struct posibilitati{long long nr,lc;}pr[1000010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>p;
    for(long long i=1;i<=p;++i)
    {
        cin>>c[i];
        pr[c[i]].lc=c[i];
    }
    if(c[1]!=1)
        c[0]=1;
    else
        nr=1;
    if(c[p]!=n)
        c[++p]=n;
    a.resize(n+5);
    for(long long i=1;i<=m;++i)
    {
        cin>>x>>y;
        a[x].push_back(y);
        ++mua[y];
    }
    for(long long i=1;i<=n;++i)
        if(mua[i]==0)
            st[++st[0]]=i;
    for(long long i=1;i<=n;++i)
    {
        for(auto x:a[st[i]])
        {
            --mua[x];
            if(mua[x]==0)
                st[++st[0]]=x;
        }
    }
    pr[1].nr=1;
    pr[1].lc=1;
    for(long long i=1;i<=n;++i)
    {
        long long q=st[i];
        if(pr[q].lc==c[nr+1])
            ++nr;
        if(pr[q].lc==c[nr])
        {
            for(auto x:a[q])
            {
                if(pr[x].lc==pr[q].lc||pr[x].lc==c[nr+1])
                {
                    pr[x].nr+=pr[q].nr;
                    if(pr[x].nr>MOD)
                        pr[x].nr-=MOD;
                }
                else if(pr[x].lc!=x)
                    pr[x]=pr[q];
            }
        }
    }
    cout<<pr[n].nr;
    return 0;
}

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