oj.uz

Submission #915813

# Submission time Handle Problem Language Result Execution time Memory
915813 2024-01-24T18:18:16 Z andrei_iorgulescu Shell (info1cup18_shell) C++14
100 / 100
 207 ms 58236 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int modulo = 1e9 + 7;
int n,m,p,drum[1000005];
vector<int>g[1000005];
int dp[1000005],cine[1000005];
bool viz[1000005];

void dfs(int nod)
{
    if (nod == n)
        dp[nod] = 1,cine[nod] = p,viz[nod] = true;
    else
    {
        viz[nod] = true;
        cine[nod] = 1e9;
        if (g[nod].size() == 0)
            return;
        for (auto vecin : g[nod])
            if (!viz[vecin])
                dfs(vecin);
        int mn = 1e9;
        for (auto vecin : g[nod])
            mn = min(mn,cine[vecin]);
        cine[nod] = mn;
        if (mn < 1e9 and drum[mn - 1] == nod)
            cine[nod]--;
        for (auto vecin : g[nod])
            if (cine[vecin] == mn)
                dp[nod] += dp[vecin];
        dp[nod] %= modulo;
        //cout << nod << ' ' << cine[nod] << ' ' << dp[nod] << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> p;
    for (int i = 1; i <= p; i++)
        cin >> drum[i];
    if (drum[p] != n)
        drum[++p] = n;
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
    }
    dfs(1);
    if (cine[1] == 1)
        cout << dp[1];
    else
        cout << 0;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29180 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29180 KB Output is correct
6 Correct 8 ms 29220 KB Output is correct
7 Correct 11 ms 29620 KB Output is correct
8 Correct 11 ms 29276 KB Output is correct
9 Correct 12 ms 29788 KB Output is correct
10 Correct 11 ms 29744 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 62 ms 38740 KB Output is correct
3 Correct 60 ms 38740 KB Output is correct
4 Correct 61 ms 38736 KB Output is correct
5 Correct 43 ms 35424 KB Output is correct
6 Correct 128 ms 51580 KB Output is correct
7 Correct 133 ms 51724 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 8 ms 29020 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Correct 8 ms 29020 KB Output is correct
5 Correct 8 ms 29180 KB Output is correct
6 Correct 8 ms 29220 KB Output is correct
7 Correct 11 ms 29620 KB Output is correct
8 Correct 11 ms 29276 KB Output is correct
9 Correct 12 ms 29788 KB Output is correct
10 Correct 11 ms 29744 KB Output is correct
11 Correct 9 ms 29272 KB Output is correct
12 Correct 62 ms 38740 KB Output is correct
13 Correct 60 ms 38740 KB Output is correct
14 Correct 61 ms 38736 KB Output is correct
15 Correct 43 ms 35424 KB Output is correct
16 Correct 128 ms 51580 KB Output is correct
17 Correct 133 ms 51724 KB Output is correct
18 Correct 194 ms 58236 KB Output is correct
19 Correct 207 ms 56636 KB Output is correct
20 Correct 180 ms 54612 KB Output is correct
21 Correct 72 ms 39796 KB Output is correct
22 Correct 194 ms 56140 KB Output is correct