oj.uz

Submission #1080549

# Submission time Handle Problem Language Result Execution time Memory
1080549 2024-08-29T10:52:14 Z batsukh2006 Shell (info1cup18_shell) C++17
100 / 100
 216 ms 76512 KB 
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
 
using namespace std;
 
#define MOD 1000000007
#define int long long
#define ss second
#define ff first
#define endl '\n'
int n,m,p;
const int mxN=1e6+1;
vector<bool> vis(mxN);
vector<int> v[mxN],c(mxN),cnt(mxN),ans(mxN);
void dfs(int a){
	vis[a]=1;
	if(a==n){
		cnt[a]=1;
		ans[a]=1;
	}else{
		for(auto node: v[a]){
			if(!vis[node]) dfs(node);
			if(cnt[node]>cnt[a]){
				cnt[a]=cnt[node];
				ans[a]=ans[node];
			}else if(cnt[node]==cnt[a]){
				ans[a]=(ans[a]+ans[node])%MOD;
			}
		}
	}
	if(a==c[p-cnt[a]+1]) cnt[a]++;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>p;
	for(int i=1; i<=p; i++) cin>>c[i];
	for(int i=1; i<=m; i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
	}
	dfs(1);
	cout<<ans[1];
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47448 KB Output is correct
2 Correct 21 ms 47452 KB Output is correct
3 Correct 21 ms 47452 KB Output is correct
4 Correct 19 ms 47452 KB Output is correct
5 Correct 26 ms 47444 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47448 KB Output is correct
2 Correct 21 ms 47452 KB Output is correct
3 Correct 21 ms 47452 KB Output is correct
4 Correct 19 ms 47452 KB Output is correct
5 Correct 26 ms 47444 KB Output is correct
6 Correct 18 ms 47452 KB Output is correct
7 Correct 20 ms 47964 KB Output is correct
8 Correct 20 ms 47712 KB Output is correct
9 Correct 22 ms 48208 KB Output is correct
10 Correct 21 ms 47964 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47452 KB Output is correct
2 Correct 73 ms 57104 KB Output is correct
3 Correct 63 ms 57084 KB Output is correct
4 Correct 76 ms 57164 KB Output is correct
5 Correct 46 ms 53944 KB Output is correct
6 Correct 123 ms 70072 KB Output is correct
7 Correct 122 ms 70228 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47448 KB Output is correct
2 Correct 21 ms 47452 KB Output is correct
3 Correct 21 ms 47452 KB Output is correct
4 Correct 19 ms 47452 KB Output is correct
5 Correct 26 ms 47444 KB Output is correct
6 Correct 18 ms 47452 KB Output is correct
7 Correct 20 ms 47964 KB Output is correct
8 Correct 20 ms 47712 KB Output is correct
9 Correct 22 ms 48208 KB Output is correct
10 Correct 21 ms 47964 KB Output is correct
11 Correct 18 ms 47452 KB Output is correct
12 Correct 73 ms 57104 KB Output is correct
13 Correct 63 ms 57084 KB Output is correct
14 Correct 76 ms 57164 KB Output is correct
15 Correct 46 ms 53944 KB Output is correct
16 Correct 123 ms 70072 KB Output is correct
17 Correct 122 ms 70228 KB Output is correct
18 Correct 216 ms 76512 KB Output is correct
19 Correct 188 ms 74820 KB Output is correct
20 Correct 181 ms 72784 KB Output is correct
21 Correct 84 ms 58292 KB Output is correct
22 Correct 193 ms 74576 KB Output is correct