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:57:37
2017-05-27 15:56:25
2017-05-27 15:52:57
2017-05-27 15:45:07
Task:Factory
Sender:Kanadan virallinen maajoukkue
Submission time:2017-05-27 15:57:37
Status:READY
Result:WRONG ANSWER

Show test data

Code

#include<iostream>
#include<queue>
#include<stack>
#include<vector>

using namespace std;

// JUST
// DO
// IT

vector<int> vl[501];
int in[501];
stack<int> alut;

void poista(int pois){
    in[pois]=-1;
    for(int seur:vl[pois]){
        in[seur]--;
        if(in[seur]==0)
            alut.push(seur);
    }
}


int main(){
    int n, m;
    cin>>n>>m;
    
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        vl[a].push_back(b);
        in[b]++;
    }
    
    for(int i=1; i<=n; i++)
        if(in[i]==0)
            alut.push(i);
            
            
    int days=0;
    while(alut.size()){
        if(alut.size()==1){
            int pois=alut.top();
            alut.pop();
            poista(pois);
            days++;
        }else{
            if(alut.size() == 2 || alut.size() >= 4){
                int p1=alut.top();
                alut.pop();
                int p2=alut.top();
                alut.pop();
                
                poista(p1);
                poista(p2);
                days++;              
            }else{
                vector<int> kaikk;
                days++;
                while(alut.size()){
                    kaikk.push_back(alut.top());
                    alut.pop();
                } 
           
                for(int i:kaikk)
                    poista(i);
                
                int paras=0;
                int lisaa=10000000;
                for(int i:kaikk){
                    int pt=0;
                    for(int seur : vl[i])
                        if(in[seur] == 0)
                            pt++;
                    if(pt<lisaa){
                        paras=i;
                        lisaa=pt;
                    }
                }
                
                in[paras]=0;
                for(int seur:vl[paras])
                    in[seur]++;
                alut = stack<int>();
                
                for(int i=1; i<=n; i++)
                    if(in[i]==0)
                        alut.push(i);
                        
                        
                   
            }
        }
    }
    
    cout<<days<<endl;
    return 0;
}