oj.uz

Submission #97931

# Submission time Handle Problem Language Result Execution time Memory
97931 2019-02-19T14:28:46 Z 314rate Shell (info1cup18_shell) C++14
100 / 100
 526 ms 48204 KB 
#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.0 / 10.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23800 KB Output is correct
2 Correct 28 ms 23808 KB Output is correct
3 Correct 30 ms 23900 KB Output is correct
4 Correct 24 ms 23936 KB Output is correct
5 Correct 25 ms 23936 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 30 ms 24192 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 36 ms 24388 KB Output is correct
10 Correct 35 ms 24312 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23892 KB Output is correct
2 Correct 126 ms 30860 KB Output is correct
3 Correct 167 ms 30956 KB Output is correct
4 Correct 123 ms 30840 KB Output is correct
5 Correct 87 ms 28536 KB Output is correct
6 Correct 269 ms 41080 KB Output is correct
7 Correct 233 ms 41080 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23800 KB Output is correct
2 Correct 28 ms 23808 KB Output is correct
3 Correct 30 ms 23900 KB Output is correct
4 Correct 24 ms 23936 KB Output is correct
5 Correct 25 ms 23936 KB Output is correct
6 Correct 24 ms 23808 KB Output is correct
7 Correct 30 ms 24192 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 36 ms 24388 KB Output is correct
10 Correct 35 ms 24312 KB Output is correct
11 Correct 32 ms 23892 KB Output is correct
12 Correct 126 ms 30860 KB Output is correct
13 Correct 167 ms 30956 KB Output is correct
14 Correct 123 ms 30840 KB Output is correct
15 Correct 87 ms 28536 KB Output is correct
16 Correct 269 ms 41080 KB Output is correct
17 Correct 233 ms 41080 KB Output is correct
18 Correct 526 ms 48204 KB Output is correct
19 Correct 501 ms 46968 KB Output is correct
20 Correct 454 ms 44920 KB Output is correct
21 Correct 141 ms 32272 KB Output is correct
22 Correct 434 ms 46280 KB Output is correct