oj.uz

Submission #301249

# Submission time Handle Problem Language Result Execution time Memory
301249 2020-09-17T18:59:10 Z marius7122 Shell (info1cup18_shell) C++14
55 / 100
 1000 ms 41240 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

vector<int> g[N], topOrd;
int n, m, p;
int ord[N], topOrdIndex[N], dp[N];
bool viz[N];

void topSort(int node)
{
    viz[node] = true;
    for(int y : g[node])
        if(!viz[y])
            topSort(y);

    topOrd.push_back(node);
}

int main()
{
    cin >> n >> m >> p;
    for(int i = 0; i < p; i++)
        cin >> ord[i];
    ord[p] = n;
    for(int i = 0; i < m; i++)
    {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
    }

	topOrd.reserve(n + 5);
    for(int i = p-1; i >= 0; i--)
        if(!viz[ord[i]])
            topSort(ord[i]);
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            topSort(i);
    reverse(topOrd.begin(), topOrd.end());


    // for(int i : topOrd)
    //  cout << i << ' ';
    // cout << '\n';

    for(int i = 0; i < topOrd.size(); i++)
        topOrdIndex[topOrd[i]] = i;


    dp[1] = 1;
    int nextStop = 0;
    for(int node : topOrd)
    {
        if(node == ord[nextStop])
        {
            if(ord[nextStop] == n)
                break;
            nextStop++;
        }

        for(int y : g[node])
            if(topOrdIndex[y] <= topOrdIndex[ord[nextStop]])
            {
                dp[y] += dp[node];
                if(dp[y] >= MOD)
                    dp[y] -= MOD;
            }
    }

    // for(int i = 1; i <= n; i++)
    //  cout << dp[i] << ' ';

    cout << dp[n] << '\n';

    return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < topOrd.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 35 ms 24184 KB Output is correct
8 Correct 25 ms 24048 KB Output is correct
9 Correct 43 ms 24312 KB Output is correct
10 Correct 42 ms 24440 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 465 ms 30996 KB Output is correct
3 Correct 458 ms 30968 KB Output is correct
4 Correct 462 ms 30968 KB Output is correct
5 Correct 300 ms 28408 KB Output is correct
6 Execution timed out 1056 ms 41240 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 35 ms 24184 KB Output is correct
8 Correct 25 ms 24048 KB Output is correct
9 Correct 43 ms 24312 KB Output is correct
10 Correct 42 ms 24440 KB Output is correct
11 Correct 19 ms 23936 KB Output is correct
12 Correct 465 ms 30996 KB Output is correct
13 Correct 458 ms 30968 KB Output is correct
14 Correct 462 ms 30968 KB Output is correct
15 Correct 300 ms 28408 KB Output is correct
16 Execution timed out 1056 ms 41240 KB Time limit exceeded
17 Halted 0 ms 0 KB -