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:52:06
2017-05-27 15:19:09
2017-05-27 15:10:10
Task:Factory
Sender:Nää jäbät
Submission time:2017-05-27 15:52:06
Status:READY
Result:WRONG ANSWER

Show test data

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