CSES - HIIT Open 2017 - Results
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.10 sdetails
#60.09 sdetails
#70.10 sdetails
#80.11 sdetails
#90.09 sdetails
#100.11 sdetails
#110.11 sdetails
#120.12 sdetails
#130.11 sdetails
#140.11 sdetails
#150.16 sdetails
#16ACCEPTED0.04 sdetails
#170.06 sdetails

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

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

Verdict:

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

correct output
413

user output
402

Verdict:

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

correct output
433

user output
427

Verdict:

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

correct output
365

user output
355

Verdict:

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

correct output
410

user output
406

Verdict:

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

correct output
372

user output
350

Verdict:

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

correct output
396

user output
387

Verdict:

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

correct output
410

user output
401

Verdict:

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

correct output
457

user output
456

Verdict:

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

correct output
364

user output
354

Verdict:

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

correct output
439

user output
436

#### Test 16

Verdict: ACCEPTED

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

correct output
5

user output
5

Verdict:

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

correct output
5

user output
6