oj.uz

Submission #363896

# Submission time Handle Problem Language Result Execution time Memory
363896 2021-02-07T13:09:13 Z ogibogi2004 Shell (info1cup18_shell) C++14
100 / 100
 818 ms 48816 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e6+6;
const ll mod=1e9+7;
int n,m,p;
vector<int>g[MAXN];
vector<int>t;
bool vis[MAXN];
void dfs(int u)
{
	vis[u]=1;
	for(auto v:g[u])
	{
		if(vis[v]==0)
		{
			dfs(v);
		}
	}
	t.push_back(u);
}
int a[MAXN];
int where[MAXN];
int w1[MAXN];
ll dp[MAXN];
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=p;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			dfs(i);
		}
	}
	reverse(t.begin(),t.end());
	for(int i=0;i<t.size();i++)where[t[i]]=i;
	/*for(int i=2;i<=p;i++)
	{
		if(where[i-1]>where[i])
		{
			cout<<"0\n";
			return 0;
		}
	}*/
	ll ans=1;
	dp[1]=1ll;
	//cout<<a[1]<<" "<<where[a[1]]<<endl;
	for(int j=where[1];j<=where[a[1]];j++)
	{
		for(auto v:g[t[j]])
		{
			if(where[v]>where[a[1]])continue;
			//cout<<t[j]<<"->"<<v<<endl;
			dp[v]+=dp[t[j]];
			dp[v]%=mod;
		}
	}
	ans*=dp[a[1]];
	//cout<<ans<<endl;
	for(ll i=2;i<=p;i++)
	{
		dp[a[i-1]]=1;
		for(int j=where[a[i-1]];j<=where[a[i]];j++)
		{
			for(auto v:g[t[j]])
			{
				if(where[v]>where[a[i]])continue;
				dp[v]+=dp[t[j]];
				dp[v]%=mod;
			}
		}
		ans*=dp[a[i]];
		ans%=mod;
		//cout<<ans<<endl;
	}
	dp[a[p]]=1;
	for(int j=where[a[p]];j<=where[n];j++)
	{
		for(auto v:g[t[j]])
		{
			if(where[v]>where[n])continue;
			dp[v]+=dp[t[j]];
			dp[v]%=mod;
		}
	}
	ans*=dp[n];
	ans%=mod;
	cout<<ans<<endl;
return 0;
}
/*
6 9 3
3 5 6
1 3
1 3
1 2
2 3
2 4
3 4
3 5
4 5
5 6
*/

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0;i<t.size();i++)where[t[i]]=i;
      |              ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 19 ms 23788 KB Output is correct
4 Correct 18 ms 23916 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 19 ms 23788 KB Output is correct
4 Correct 18 ms 23916 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 27 ms 24172 KB Output is correct
8 Correct 22 ms 24044 KB Output is correct
9 Correct 35 ms 24428 KB Output is correct
10 Correct 36 ms 24416 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23916 KB Output is correct
2 Correct 274 ms 26732 KB Output is correct
3 Correct 269 ms 26824 KB Output is correct
4 Correct 264 ms 26732 KB Output is correct
5 Correct 175 ms 26220 KB Output is correct
6 Correct 616 ms 31084 KB Output is correct
7 Correct 599 ms 30956 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 19 ms 23788 KB Output is correct
4 Correct 18 ms 23916 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 27 ms 24172 KB Output is correct
8 Correct 22 ms 24044 KB Output is correct
9 Correct 35 ms 24428 KB Output is correct
10 Correct 36 ms 24416 KB Output is correct
11 Correct 19 ms 23916 KB Output is correct
12 Correct 274 ms 26732 KB Output is correct
13 Correct 269 ms 26824 KB Output is correct
14 Correct 264 ms 26732 KB Output is correct
15 Correct 175 ms 26220 KB Output is correct
16 Correct 616 ms 31084 KB Output is correct
17 Correct 599 ms 30956 KB Output is correct
18 Correct 818 ms 48816 KB Output is correct
19 Correct 785 ms 47592 KB Output is correct
20 Correct 806 ms 45456 KB Output is correct
21 Correct 318 ms 32460 KB Output is correct
22 Correct 785 ms 46700 KB Output is correct