Factory

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v[501];
vector<int> rv[501];
int vc[501];
int vd[501];
int vs[501];
 
int main() {
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        v[b].push_back(a);
        rv[a].push_back(b);
    }
    queue<int> q;
    for(int i=0;i<n;i++) {
        if(v[i].size() == 0)
            q.push(i);
        vc[i] = v[i].size();
    }
    vector<int> sorted(n);
    int j=n-1;
    while(q.size() > 0) {
        int i = q.front();
        q.pop();
        sorted[j--]=i;
        for(auto& it : rv[i]){
            if(!--vc[it])q.push(it);
        }
    }
    priority_queue<tuple<int,int,int>> pq;
    for(auto& i : sorted){
        vd[i]=1;
        vs[i]=1;
        for(auto& it : rv[i]){
            vs[i]+=vs[it];
            if(vd[i]<vd[it]+1)vd[i]=vd[it]+1;
        }
        vc[i]=v[i].size();
        if(vc[i]==0)pq.emplace(vd[i],vs[i],i);
    }
    int r=0;
    int mr=0;
    while(pq.size() > 0){
        int p,v,i;
        tie(p,v,i) = pq.top();
        pq.pop();
        if(mr==1)mr=0;
        else if(pq.size()>0)mr=1,++r;
        else ++r;
        for(auto& it : rv[i]){
            if(!--vc[it])pq.emplace(vd[it],vs[it],it);
        }
    }
    cout<<r<<'\n';
    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: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER