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:58:18
2017-05-27 15:58:18
2017-05-27 15:50:38
2017-05-27 15:49:07
2017-05-27 15:36:56
2017-05-27 15:33:46
Task:Factory
Sender:Ace of Spades
Submission time:2017-05-27 15:58:18
Status:READY
Result:WRONG ANSWER

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:21:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < jo.size(); ++i) {
                                ^
input/code.cpp:23:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < v[x].size(); ++j) {
                               ^

Code

#include <bits/stdc++.h>
using namespace std;
const int MN = 555;
int in_cnt[MN];
vector<int> v[MN];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; ++i) {
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	++in_cnt[b];
    }
    vector<int> jo;
    for(int i = 1; i <= n; ++i) {
	if(in_cnt[i] == 0) {
	    jo.push_back(i);
	}
    }
    for(int i = 0; i < jo.size(); ++i) {
	int x = jo[i];
	for(int j = 0; j < v[x].size(); ++j) {
	    int y = v[x][j];
	    --in_cnt[y];
	    if(in_cnt[y] == 0) {
		jo.push_back(y);
	    }
	}
    }
    for(int i = 1; i <= n; ++i) {
	if(in_cnt[i]) {
	    cout<<"LUL\n";
	    while(1);
	}
    }
    for(int i = 1; i <= n; ++i) {
	for(auto x: v[i]) {
	    ++in_cnt[x];
	}
    }
    int ans = 0;
    int jonne[MN] = {0};
    bool visited[MN] = {0};
    for(int i = (int)jo.size()-1; i >= 0; --i) {
	int x = jo[i];
	for(auto y: v[x]) {
	    jonne[x] += jonne[y];
	}
	jonne[x]++;
    }
    /*
    cout<<'\n'<<'\n';
    for(int i = 1; i <= n; ++i) {
	cout<<i<<' '<<jonne[i]<<'\n';
    }
    cout<<'\n';
    */
    int ans2 = 1e9;
    for(int i = 0; i < 500; ++i) {
	ans = 0;
	while(1) {
	    vector<pair<int, int> > v2;
	    for(int i = 1; i <= n; ++i) {
		if(!visited[i] && in_cnt[i] == 0) {
		    v2.push_back({jonne[i], i});
		}
	    }
	    if(v2.size() == 0) {
		break;
	    }
	    ++ans;
	    sort(v2.begin(), v2.end());
	    for(int i = 0; i < 2; ++i) {
		if(v2.size()) {
		    int x = v2.back().second;
		    v2.pop_back();
		    visited[x] = 1;
		    for(auto y: v[x]) {
			--in_cnt[y];
		    }
		}
	    }
	}
	ans2 = min(ans, ans2);
    }
    cout<<ans2<<endl;
}