oj.uz

Submission #987036

# Submission time Handle Problem Language Result Execution time Memory
987036 2024-05-21T17:55:45 Z Kevin_Jao Shell (info1cup18_shell) C++14
100 / 100
 197 ms 76624 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 12 ms 47448 KB Output is correct
2 Correct 12 ms 47452 KB Output is correct
3 Correct 12 ms 47576 KB Output is correct
4 Correct 14 ms 47444 KB Output is correct
5 Correct 13 ms 47452 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47448 KB Output is correct
2 Correct 12 ms 47452 KB Output is correct
3 Correct 12 ms 47576 KB Output is correct
4 Correct 14 ms 47444 KB Output is correct
5 Correct 13 ms 47452 KB Output is correct
6 Correct 14 ms 47588 KB Output is correct
7 Correct 17 ms 48216 KB Output is correct
8 Correct 15 ms 47684 KB Output is correct
9 Correct 18 ms 48228 KB Output is correct
10 Correct 18 ms 47964 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 47452 KB Output is correct
2 Correct 66 ms 56972 KB Output is correct
3 Correct 63 ms 57172 KB Output is correct
4 Correct 66 ms 57172 KB Output is correct
5 Correct 47 ms 53840 KB Output is correct
6 Correct 131 ms 70132 KB Output is correct
7 Correct 128 ms 70228 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 47448 KB Output is correct
2 Correct 12 ms 47452 KB Output is correct
3 Correct 12 ms 47576 KB Output is correct
4 Correct 14 ms 47444 KB Output is correct
5 Correct 13 ms 47452 KB Output is correct
6 Correct 14 ms 47588 KB Output is correct
7 Correct 17 ms 48216 KB Output is correct
8 Correct 15 ms 47684 KB Output is correct
9 Correct 18 ms 48228 KB Output is correct
10 Correct 18 ms 47964 KB Output is correct
11 Correct 14 ms 47452 KB Output is correct
12 Correct 66 ms 56972 KB Output is correct
13 Correct 63 ms 57172 KB Output is correct
14 Correct 66 ms 57172 KB Output is correct
15 Correct 47 ms 53840 KB Output is correct
16 Correct 131 ms 70132 KB Output is correct
17 Correct 128 ms 70228 KB Output is correct
18 Correct 193 ms 76624 KB Output is correct
19 Correct 197 ms 74952 KB Output is correct
20 Correct 174 ms 72812 KB Output is correct
21 Correct 76 ms 58192 KB Output is correct
22 Correct 190 ms 74588 KB Output is correct