oj.uz

Submission #691001

# Submission time Handle Problem Language Result Execution time Memory
691001 2023-01-30T20:24:54 Z divad Shell (info1cup18_shell) C++14
100 / 100
 230 ms 48496 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
#define MAX 1000002
using namespace std;
int n,m,p,x,y,dp[MAX],cnt[MAX],mrc[MAX];
/// dp[nod] = in ce nod trebuie sa merg
/// cnt[nod] = cate drumuri sunt
vector<int> v[MAX];

void dfs(int nod){
    if(nod == n){
        dp[nod] = 1;
        cnt[nod] = 1;
        if(nod == mrc[p-dp[nod]+1]){
            dp[nod]++;
        }
    }else{
        for(int vecin: v[nod]){
            if(dp[vecin] == 0){
                dfs(vecin);
            }
            if(dp[vecin] > dp[nod]){
                dp[nod] = dp[vecin];
                cnt[nod] = cnt[vecin];
            }else if(dp[vecin] == dp[nod]){
                cnt[nod] += cnt[vecin];
            }
            cnt[nod] %= MOD;
        }
        if(nod == mrc[p-dp[nod]+1]){
            dp[nod]++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> p;
    for(int i = 1; i <= p; i++){
        cin >> mrc[i];
    }
    for(int i = 1; i <= m; i++){
        cin >> x >> y;
        v[x].push_back(y);
    }
    dfs(1);
    cout << cnt[1];
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23824 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23824 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23796 KB Output is correct
7 Correct 16 ms 24204 KB Output is correct
8 Correct 14 ms 23920 KB Output is correct
9 Correct 17 ms 24276 KB Output is correct
10 Correct 18 ms 24268 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23804 KB Output is correct
2 Correct 71 ms 26444 KB Output is correct
3 Correct 73 ms 26512 KB Output is correct
4 Correct 76 ms 30792 KB Output is correct
5 Correct 52 ms 28340 KB Output is correct
6 Correct 159 ms 40852 KB Output is correct
7 Correct 167 ms 41000 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23824 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23776 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23796 KB Output is correct
7 Correct 16 ms 24204 KB Output is correct
8 Correct 14 ms 23920 KB Output is correct
9 Correct 17 ms 24276 KB Output is correct
10 Correct 18 ms 24268 KB Output is correct
11 Correct 13 ms 23804 KB Output is correct
12 Correct 71 ms 26444 KB Output is correct
13 Correct 73 ms 26512 KB Output is correct
14 Correct 76 ms 30792 KB Output is correct
15 Correct 52 ms 28340 KB Output is correct
16 Correct 159 ms 40852 KB Output is correct
17 Correct 167 ms 41000 KB Output is correct
18 Correct 230 ms 48496 KB Output is correct
19 Correct 224 ms 46964 KB Output is correct
20 Correct 223 ms 44376 KB Output is correct
21 Correct 92 ms 32076 KB Output is correct
22 Correct 225 ms 45716 KB Output is correct