Submission #301249

#	Time	Username	Problem	Language	Result	Execution time	Memory
301249		marius7122	Shell (info1cup18_shell)	C++14	55 / 100	1056 ms	41240 KiB

shell

#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 (stderr)

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 / 10
• Subtask 2: 45 / 45
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25