Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 14:13:46
Task:Monotonic
Sender:Ukkonen Fan Club
Submission time:2018-05-26 14:13:46
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.01 / 2.00details
#2ACCEPTED0.23 / 2.00details
#3ACCEPTED0.34 / 2.00details
#4ACCEPTED1.46 / 2.00details
#5ACCEPTED0.17 / 2.00details
#6ACCEPTED0.19 / 2.00details
#7ACCEPTED0.26 / 2.00details
#8ACCEPTED0.30 / 2.00details
#9ACCEPTED0.10 / 2.00details
#10ACCEPTED0.09 / 2.00details

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();
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
3
4 4
1 2
3 4
1 2
3 4
4 3
1 2
2 3
3 4
2 1
1 2
view   save

correct output
-1
3
1
view   save

user output
-1
3
1
view   save

Test 2

Verdict: ACCEPTED

input
10
15 200
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
view   save

Test 3

Verdict: ACCEPTED

input
10
15 350
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
3
-1
2
-1
1
2
2
2
-1
-1
view   save

user output
3
-1
2
-1
1
2
2
2
-1
-1
view   save

Test 4

Verdict: ACCEPTED

input
10
15 1500
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
1
1
1
1
1
1
1
1
1
1
view   save

user output
1
1
1
1
1
1
1
1
1
1
view   save

Test 5

Verdict: ACCEPTED

input
10
15 100
4 10
3 9
6 15
8 10
10 11
2 10
1 15
8 14
5 9
4 12
8 9
9 14
7 8
11 14
3 4
3 11
14 15
7 9
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

Test 6

Verdict: ACCEPTED

input
10
15 200
4 5
2 12
7 8
2 3
1 2
7 9
5 15
1 13
4 9
6 9
5 13
3 14
2 5
4 15
1 14
11 13
5 13
4 5
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

Test 7

Verdict: ACCEPTED

input
10
15 300
5 10
6 12
12 13
12 14
11 15
1 9
8 14
4 13
1 11
3 15
2 6
8 14
4 7
2 9
4 10
1 12
4 7
3 5
...
view   save

correct output
-1
-1
2
2
-1
2
-1
2
-1
-1
view   save

user output
-1
-1
2
2
-1
2
-1
2
-1
-1
view   save

Test 8

Verdict: ACCEPTED

input
10
15 400
10 13
2 14
8 13
1 5
1 3
10 11
8 13
6 12
6 13
1 5
8 13
4 12
7 14
9 15
9 11
2 4
9 10
12 13
...
view   save

correct output
-1
1
1
-1
1
2
2
2
1
2
view   save

user output
-1
1
1
-1
1
2
2
2
1
2
view   save

Test 9

Verdict: ACCEPTED

input
10
15 14
14 15
11 12
1 2
13 14
7 8
6 7
4 5
9 10
8 9
12 13
5 6
2 3
10 11
3 4
15 28
3 4
4 5
12 13
...
view   save

correct output
8
7
4
4
3
3
2
2
2
2
view   save

user output
8
7
4
4
3
3
2
2
2
2
view   save

Test 10

Verdict: ACCEPTED

input
10
15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 28
1 2
2 3
3 4
...
view   save

correct output
14
7
5
4
3
3
2
2
2
2
view   save

user output
14
7
5
4
3
3
2
2
2
2
view   save