oj.uz

Submission #96025

# Submission time Handle Problem Language Result Execution time Memory
96025 2019-02-05T10:07:27 Z alextodoran Shell (info1cup18_shell) C++14
100 / 100
 741 ms 172996 KB 
#include <bits/stdc++.h>

#define NM 3000002
#define ll long long

using namespace std;

const ll MOD = 1e9+7;

vector <int> ine[NM], oute[NM];

int n, m, p;

int v[NM];
bool spv[NM];

int g[NM];

queue <int> q;

int ord[NM];

int vo[NM];

bool fs (int a, int b)
{
    return ord[a] < ord[b];
}

ll dp[NM];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> p;
    for(int i = 1; i <= p; i++)
    {
        cin >> v[i];
        spv[v[i]] = 1;
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ine[v].push_back(u);
        oute[u].push_back(v);
        g[v]++;
    }
    for(int i = 1; i <= n; i++)
        if(g[i] == 0)
        {
            ord[i] = 1;
            q.push(i);
        }
    while(!q.empty())
    {
        auto f = q.front();
        q.pop();
        for(auto e : oute[f])
        {
            g[e]--;
            if(g[e] == 0)
            {
                ord[e] = ord[f] + 1;
                q.push(e);
            }
        }
    }
    for(int i = 2; i <= p; i++)
        if(ord[v[i]] <= ord[v[i - 1]])
        {
            cout << "0\n";
            return 0;
        }
    for(int i = 1; i <= n; i++)
        vo[i] = i;
    sort(vo + 1, vo + n + 1, fs);
    int last = 0;
    for(int i = 1; i <= n; i++)
        if(vo[i] != 1)
        {
            if(last != 0)
                for(auto e : ine[vo[i]])
                    if(ord[e] > ord[last] || e == last)
                    {
                        dp[vo[i]] += dp[e];
                        if(dp[vo[i]] >= MOD)
                            dp[vo[i]] -= MOD;
                    }
            if(spv[vo[i]])
                last = vo[i];
        }
        else
        {
            if(last == 0)
                dp[1] = 1;
            last = 1;
        }
    cout << dp[n] << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 141304 KB Output is correct
2 Correct 110 ms 141360 KB Output is correct
3 Correct 108 ms 141364 KB Output is correct
4 Correct 111 ms 141308 KB Output is correct
5 Correct 109 ms 141348 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 141304 KB Output is correct
2 Correct 110 ms 141360 KB Output is correct
3 Correct 108 ms 141364 KB Output is correct
4 Correct 111 ms 141308 KB Output is correct
5 Correct 109 ms 141348 KB Output is correct
6 Correct 107 ms 141304 KB Output is correct
7 Correct 114 ms 141796 KB Output is correct
8 Correct 113 ms 141660 KB Output is correct
9 Correct 134 ms 141816 KB Output is correct
10 Correct 136 ms 141816 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 141428 KB Output is correct
2 Correct 210 ms 146708 KB Output is correct
3 Correct 210 ms 146804 KB Output is correct
4 Correct 207 ms 146808 KB Output is correct
5 Correct 180 ms 145272 KB Output is correct
6 Correct 326 ms 154716 KB Output is correct
7 Correct 326 ms 154624 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 141304 KB Output is correct
2 Correct 110 ms 141360 KB Output is correct
3 Correct 108 ms 141364 KB Output is correct
4 Correct 111 ms 141308 KB Output is correct
5 Correct 109 ms 141348 KB Output is correct
6 Correct 107 ms 141304 KB Output is correct
7 Correct 114 ms 141796 KB Output is correct
8 Correct 113 ms 141660 KB Output is correct
9 Correct 134 ms 141816 KB Output is correct
10 Correct 136 ms 141816 KB Output is correct
11 Correct 133 ms 141428 KB Output is correct
12 Correct 210 ms 146708 KB Output is correct
13 Correct 210 ms 146804 KB Output is correct
14 Correct 207 ms 146808 KB Output is correct
15 Correct 180 ms 145272 KB Output is correct
16 Correct 326 ms 154716 KB Output is correct
17 Correct 326 ms 154624 KB Output is correct
18 Correct 633 ms 172996 KB Output is correct
19 Correct 593 ms 171768 KB Output is correct
20 Correct 643 ms 171300 KB Output is correct
21 Correct 239 ms 153168 KB Output is correct
22 Correct 741 ms 172148 KB Output is correct