Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 14:13:46
Task:Monotonic
Sender:Ukkonen Fan Club
Submission time:2018-05-26 14:13:46
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
vector<pair<int, int> > prog;
int transition[1<<15];
void solve() {
	int n,m;
	cin>>n>>m;
	prog.resize(m);
	for(int i = 0; i < m; ++i) {
		cin>>prog[i].F>>prog[i].S;
		--prog[i].F;
		--prog[i].S;
	}
	for(int mask = 0; mask < (1<<n); ++mask) {
		int mask2 = mask;
		for(int i = 0; i < m; ++i) {
			int a = 1<<prog[i].F;
			int b = 1<<prog[i].S;
			if((mask2 & a) && (!(mask2&b))) {
				mask2 ^= a | b;
			}
		}
		transition[mask] = mask2;
	}
	int ma = 0;
	for(int mask = 0; mask < (1<<n); ++mask) {
		int mask2 = mask;
		int ones = __builtin_popcount(mask);
		int zeros = n - ones;
		int res = (1<<ones)-1;
		res <<= zeros;
		int moves = 0;
		for(int i = 0; i < 250; ++i) {
			if(mask2 == res) break;
			++moves;
			mask2 = transition[mask2];
		}
		ma = max(ma, moves);
	}
	if(ma == 250) ma = -1;

	cout<<ma<<'\n';
}
int main() {
	int tt;
	cin>>tt;
	for(int xx = 0; xx < tt; ++xx) {
		solve();
	}
}