CSES - HIIT Open 2017 - Results
Submission details
Task:Factory
Sender:Nää jäbät
Submission time:2017-05-27 15:52:06 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.07 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.08 sdetails
#6ACCEPTED0.05 sdetails
#7ACCEPTED0.06 sdetails
#80.07 sdetails
#9ACCEPTED0.06 sdetails
#100.09 sdetails
#11ACCEPTED0.06 sdetails
#12ACCEPTED0.06 sdetails
#13ACCEPTED0.07 sdetails
#140.06 sdetails
#15ACCEPTED0.07 sdetails
#16ACCEPTED0.04 sdetails
#17ACCEPTED0.05 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:59:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int s = 0; s < members[g].size(); ++s) {
                                             ^
input/code.cpp:61:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < members[g+1].size(); ++j) {
                                                   ^

Code

#include <iostream>
#include <vector>
#include <utility>

const int N = 500;
bool need [N][N];
std::vector<int> members [N];
std::vector<bool> targets [N];
int possibles [N];
int ins [N];
int level [N];
bool canCost [N];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        --a;
        --b;
        need[a][b] = true;
        ++ins[b];
    }
    std::vector<int> topo;
    for (int i = 0; i < n; ++i) {
        if (ins[i] == 0) {
            topo.push_back(i);
            members[0].push_back(i);
            targets[0].push_back(false);
        }
    }
    for (int i = 0; i < n; ++i) {
        int num = topo[i];
        for (int j = 0; j < n; ++j) {
            if (need[num][j]) {
                --ins[j];
                if (ins[j] == 0) {
                    level[j] = level[num] + 1;
                    topo.push_back(j);
                    members[level[j]].push_back(j);
                    targets[level[j]].push_back(false);
                }
            }
        }
    }

    /*
    for (int i = 0; i < n; ++i) {
        std::cout << level[i] << ' ';
    }
    std::cout << '\n';
    */
    int maxl = level[topo[n-1]] + 1;
    for (int g = maxl - 2; g >= 0; --g) {
        for (int s = 0; s < members[g].size(); ++s) {
            int num = members[g][s];
            for (int j = 0; j < members[g+1].size(); ++j) {
                int t = members[g+1][j];
                if (! need[num][t]) {
                    //std::cout << num << ' ';
                    if (possibles[g+1] >= 2) {
                        targets[g][s] = true;
                        ++possibles[g];
                        break;
                        //std::cout << "A\n";
                    } else if (! targets[g+1][j]) {
                        targets[g][s] = true;
                        ++possibles[g];
                        break;
                        //std::cout << "B\n";
                    } else {
                        canCost[g] = true;
                    }
                }
            }
        }
    }
    int count = 0;
    int used = 0;
    bool canDo = true;
    for (int g = 0; g < maxl; ++g) {
        int amount = members[g].size() - used;
        if (amount & 1) {
            bool haslast = (possibles[g] > 0);
            if (canDo && canCost[g] && (! haslast)) {
                canDo = false;
                count += (amount + 1) / 2;
                used = 1;
            } else if (canDo && haslast) {
                count += (amount + 1) / 2;
                used = 1;
            } else {
                canDo = true;
                count += (amount + 1) / 2;
                used = 0;
            }
        } else {
            count += amount / 2;
            used = 0;
            canDo = true;
        }
    }
    std::cout << count << '\n';
}

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