oj.uz

Submission #95345

# Submission time Handle Problem Language Result Execution time Memory
95345 2019-01-30T13:32:01 Z dalgerok Shell (info1cup18_shell) C++14
100 / 100
 350 ms 47844 KB 
#include<bits/stdc++.h>
using namespace std;



const int N = 1e6 + 5, MOD = 1e9 + 7;



int n, m, p, a[N], dp[N], ans[N];
vector < int > g[N];

void dfs(int v){
    if(v == n){
        dp[v] = ans[v] = 1;
    }
    else{
        for(int to : g[v]){
            if(dp[to] == 0){
                dfs(to);
            }
            if(dp[to] > dp[v]){
                dp[v] = dp[to];
                ans[v] = ans[to];
            }
            else if(dp[to] == dp[v]){
                ans[v] += ans[to];
                if(ans[v] >= MOD){
                    ans[v] -= MOD;
                }
            }
        }
    }
    if(v == a[p - dp[v] + 1]){
        dp[v] += 1;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> p;
    for(int i = 1; i <= p; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }
    dfs(1);
    cout << ans[1];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 29 ms 24312 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 97 ms 30840 KB Output is correct
3 Correct 95 ms 31000 KB Output is correct
4 Correct 93 ms 30800 KB Output is correct
5 Correct 71 ms 28508 KB Output is correct
6 Correct 212 ms 41116 KB Output is correct
7 Correct 192 ms 40952 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 23 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 29 ms 24312 KB Output is correct
11 Correct 23 ms 23928 KB Output is correct
12 Correct 97 ms 30840 KB Output is correct
13 Correct 95 ms 31000 KB Output is correct
14 Correct 93 ms 30800 KB Output is correct
15 Correct 71 ms 28508 KB Output is correct
16 Correct 212 ms 41116 KB Output is correct
17 Correct 192 ms 40952 KB Output is correct
18 Correct 350 ms 47844 KB Output is correct
19 Correct 322 ms 46328 KB Output is correct
20 Correct 310 ms 44724 KB Output is correct
21 Correct 122 ms 32248 KB Output is correct
22 Correct 290 ms 45816 KB Output is correct