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 11:53:18
2017-05-27 11:46:10
Task:Factory
Sender:kyy-kol
Submission time:2017-05-27 11:53:18
Status:READY
Result:WRONG ANSWER

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:49:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ts.size(); ++i) {
                                 ^

Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
typedef vector<int> vi;
#define PB push_back

int n, m;
vi g[505];

vi ts;
int v1[505];
int comp[505];

vector<int> cws;

int v7[505];

void dfs1(int s) {
    if (v1[s]) return;
    v1[s] = 1;
    for (int a : g[s]) {
        dfs1(a);
    }
    ts.push_back(s);
}

void dfs2(int s, int cc) {
    if (comp[s]) return;
    comp[s] = cc;
    for (int a : g[s]) {
        dfs2(a, cc);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }
    for (int i = 1; i <= n; ++i) dfs1(i);
    reverse(ts.begin(), ts.end());
    
    int ccomp = 0;
    for (int i = 0; i < ts.size(); ++i) {
        int cur = ts[i];
        if (comp[cur] == 0) {
            ccomp++;
            dfs2(cur, ccomp);
            cws.PB(cur);
        }
    }
    
    int res = 0;
    while (cws.size() != 0) {
        int c1 = cws[cws.size()-1];
        cws.pop_back();
        v7[c1] = 1;
        
        int c2 = -1;
        if (cws.size() != 0)  {
            c2 = cws[cws.size()-1];
            cws.pop_back();
            v7[c2] = 1;
        }
        
        res++;
        for (int a : g[c1]) {
            if (v7[a] == 0) {
                v7[a] = 1;
                cws.PB(a);
            }
        }
        if (c2 != -1) {
            for (int b : g[c2]) {
                if (v7[b] == 0) {
                    v7[b] = 1;
                    cws.PB(b);
                }
            }
        }
    }
    cout << res << "\n";
    return 0;
}