CSES - HIIT Open 2017 - Results
Submission details
Task:Factory
Sender:Kanadan virallinen maajoukkue
Submission time:2017-05-27 15:45:07 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.03 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.06 sdetails
#5ACCEPTED0.10 sdetails
#6ACCEPTED0.13 sdetails
#7ACCEPTED0.13 sdetails
#80.10 sdetails
#9ACCEPTED0.11 sdetails
#100.07 sdetails
#11ACCEPTED0.13 sdetails
#12ACCEPTED0.12 sdetails
#13ACCEPTED0.10 sdetails
#140.09 sdetails
#15ACCEPTED0.08 sdetails
#16ACCEPTED0.05 sdetails
#17ACCEPTED0.06 sdetails

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{
            days+=alut.size()/2;
            vector<int> kaikk;
            
            
            while(alut.size()){
                kaikk.push_back(alut.top());
                alut.pop();
            }
            
            if(kaikk.size()%2==0){
                for(int i:kaikk)
                    poista(i);
            }else{
                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;
}

Test details

Test 1

Verdict: ACCEPTED

input
1 0

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

input
2 0

correct output
1

user output
1

Test 3

Verdict: ACCEPTED

input
2 1
2 1

correct output
2

user output
2

Test 4

Verdict: ACCEPTED

input
500 0

correct output
250

user output
250

Test 5

Verdict: ACCEPTED

input
500 124750
66 104
50 159
173 457
200 154
...

correct output
500

user output
500

Test 6

Verdict: ACCEPTED

input
500 96771
376 390
243 497
417 360
107 80
...

correct output
413

user output
413

Test 7

Verdict: ACCEPTED

input
500 106799
96 245
68 62
122 119
460 454
...

correct output
433

user output
433

Test 8

Verdict:

input
500 83550
76 338
111 174
88 142
114 463
...

correct output
365

user output
366

Test 9

Verdict: ACCEPTED

input
500 98051
281 60
312 284
270 474
385 224
...

correct output
410

user output
410

Test 10

Verdict:

input
500 86622
5 320
50 107
182 483
385 500
...

correct output
372

user output
373

Test 11

Verdict: ACCEPTED

input
500 99445
421 286
392 406
155 290
475 453
...

correct output
396

user output
396

Test 12

Verdict: ACCEPTED

input
500 99832
283 149
315 396
264 422
224 388
...

correct output
410

user output
410

Test 13

Verdict: ACCEPTED

input
500 116149
446 185
232 35
498 391
189 63
...

correct output
457

user output
457

Test 14

Verdict:

input
500 84757
71 205
286 360
184 486
30 228
...

correct output
364

user output
365

Test 15

Verdict: ACCEPTED

input
500 108617
126 250
76 224
449 69
200 63
...

correct output
439

user output
439

Test 16

Verdict: ACCEPTED

input
10 20
7 8
1 3
4 8
5 9
...

correct output
5

user output
5

Test 17

Verdict: ACCEPTED

input
10 20
2 9
9 8
4 3
7 3
...

correct output
5

user output
5