Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


History
2017-05-27 15:39:50
Task:Factory
Sender:KnowYourArchitecture
Submission time:2017-05-27 15:39:50
Status:READY
Result:WRONG ANSWER

Show test data

Code

#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;
}