oj.uz

Submission #988136

# Submission time Handle Problem Language Result Execution time Memory
988136 2024-05-24T06:15:50 Z Kevin_Jao Shell (info1cup18_shell) C++17
100 / 100
 259 ms 76372 KB 
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<utility>
#include<iomanip>
#include<string.h>
#include<limits.h>
#include<algorithm>
#include<functional>
#include<unordered_map> 
using namespace std;
#define MOD 1000000007
#define int long long
#define ss second
#define ff first
#define endl '\n'
int t;
int n,m,p;
const int mxN=1e6+5;
vector<bool> vis(mxN);
vector<int> v[mxN],c(mxN),cnt(mxN),ans(mxN);
void dfs(int a){
	vis[a]=1;
	if(a==t){
		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;
	int chk; cin>>chk;
	if(chk==1){
		c[1]=1;
		for(int i=2; i<=p; i++) cin>>c[i];
		if(c[p]!=n) c[++p]=n;
	}else{
		p++;
		c[1]=1;
		c[2]=chk;
		for(int i=3; i<=p; i++) cin>>c[i];
		if(c[p]!=n) c[++p]=n;
	}
	t=c[p];
	for(int i=1; i<=m; i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
	}
	dfs(c[1]);
	cout<<ans[c[1]];
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47444 KB Output is correct
2 Correct 26 ms 47452 KB Output is correct
3 Correct 30 ms 47432 KB Output is correct
4 Correct 29 ms 47696 KB Output is correct
5 Correct 28 ms 47436 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47444 KB Output is correct
2 Correct 26 ms 47452 KB Output is correct
3 Correct 30 ms 47432 KB Output is correct
4 Correct 29 ms 47696 KB Output is correct
5 Correct 28 ms 47436 KB Output is correct
6 Correct 24 ms 47704 KB Output is correct
7 Correct 31 ms 47964 KB Output is correct
8 Correct 29 ms 47700 KB Output is correct
9 Correct 31 ms 48212 KB Output is correct
10 Correct 36 ms 48036 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47452 KB Output is correct
2 Correct 78 ms 52816 KB Output is correct
3 Correct 77 ms 52868 KB Output is correct
4 Correct 76 ms 52820 KB Output is correct
5 Correct 61 ms 53840 KB Output is correct
6 Correct 149 ms 70172 KB Output is correct
7 Correct 148 ms 70028 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47444 KB Output is correct
2 Correct 26 ms 47452 KB Output is correct
3 Correct 30 ms 47432 KB Output is correct
4 Correct 29 ms 47696 KB Output is correct
5 Correct 28 ms 47436 KB Output is correct
6 Correct 24 ms 47704 KB Output is correct
7 Correct 31 ms 47964 KB Output is correct
8 Correct 29 ms 47700 KB Output is correct
9 Correct 31 ms 48212 KB Output is correct
10 Correct 36 ms 48036 KB Output is correct
11 Correct 27 ms 47452 KB Output is correct
12 Correct 78 ms 52816 KB Output is correct
13 Correct 77 ms 52868 KB Output is correct
14 Correct 76 ms 52820 KB Output is correct
15 Correct 61 ms 53840 KB Output is correct
16 Correct 149 ms 70172 KB Output is correct
17 Correct 148 ms 70028 KB Output is correct
18 Correct 230 ms 76372 KB Output is correct
19 Correct 210 ms 74720 KB Output is correct
20 Correct 259 ms 72772 KB Output is correct
21 Correct 92 ms 58320 KB Output is correct
22 Correct 213 ms 74576 KB Output is correct