Factory

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main(){
    int nVertices, nEdges;
    cin >> nVertices >> nEdges;
    vector<vector<int> > children(nVertices);
    vector<vector<int> > parents(nVertices);
    vector<int> temp_out_degrees(nVertices);
    vector<int> temp_in_degrees(nVertices);

    for(int i = 0; i < nEdges; i++){
        int from, to;
        cin >> from >> to; from--; to--;
        children[from].push_back(to);
        parents[to].push_back(from);
        temp_out_degrees[from]++;
        temp_in_degrees[to]++;
    }
    
    vector<int> lengths(nVertices);
    vector<int> Q;

    for(int i = 0; i < nVertices; i++){
        if(temp_out_degrees[i] == 0){
            Q.push_back(i);
            lengths[i] = 1;
        }
    }
    
    while(Q.size() > 0){
        int v = Q.back(); Q.pop_back();
        for(int p : parents[v]){
            temp_out_degrees[p]--;
            if(temp_out_degrees[p] == 0){
                int length = 0;
                for(int c : children[p]){
                    length = max(length, lengths[c]+1);
                }
                lengths[p] = length;
                Q.push_back(p);
            }
        }
    }
    
    set<pair<int,int> > prioQ;
    for(int i = 0; i < nVertices; i++){
        if(parents[i].size() == 0){
            prioQ.insert({-lengths[i], i});
        }
    }
    
    for(int day = 1; ; day++){
        // Take up to two jobs
        int j1 = prioQ.begin()->second;
        prioQ.erase(prioQ.begin());
        int j2 = -1;
        if(prioQ.size() > 0){
            j2 = prioQ.begin()->second;
            prioQ.erase(prioQ.begin());
        }
        
        // Push children
        for(int v : children[j1]){
            temp_in_degrees[v]--;
            if(temp_in_degrees[v] == 0)
                prioQ.insert({-lengths[v],v});
        }
        if(j2 != -1){
            for(int v : children[j2]){
                temp_in_degrees[v]--;
                if(temp_in_degrees[v] == 0)
                    prioQ.insert({-lengths[v],v});
            }
        }
        
        if(prioQ.size() == 0){
            cout << day << endl;
            return 0;
        }
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER