CSES - HIIT Open 2018 - Results
Submission details
Task:Monotonic
Sender:KnowYourArchitecture
Submission time:2018-05-26 15:02:00
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#20.02 sdetails
#30.02 sdetails
#4ACCEPTED0.02 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#10ACCEPTED0.01 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

constexpr int N = 1000;
constexpr int M = 15;

mt19937 rnd;

typedef pair<int, int> op;

template<typename T>
void exec(vector<T> &v, vector<op> ops) {
	for (auto o : ops) {
		if (v[o.first] > v[o.second]) {
			swap(v[o.first], v[o.second]);
		}
	}
}

template<typename T>
bool isOrder(const vector<T> &v) {
	for(size_t i = 1; i < v.size(); i++) {
		if (!(v[i-1] < v[i])) return false;
	}
	return true;
}

inline bool ready(vector<int> &v, int n) {
	int mask = (1 << (n)) - 1;
	for (int a : v) {
		if ((a & mask) != mask) return false;
	}
	return true;
}

void test() {
	int n, m;
	cin >> n >> m;
	vector<int> v(n);
	vector<op> ops(m);
	for (auto &o : ops) {
		cin >> o.first >> o.second;
		o.first--;
		o.second--;
	}
	
	// Init v
	for (int i = 0; i < n; i++) {
		v[i] = 1<<i;
	}
	
	// Iterate until ready
	int k = 0;
	while (!ready(v, n) && k++ < 16) {
		for (auto o : ops) {
			v[o.first] = v[o.second] = v[o.first] | v[o.second];
		}
	}
	if (!ready(v, n)) {
		cout << "-1\n";
	} else {
		cout << k << "\n";
	}
}

int main(){
	int t;
	cin>>t;
	while(t--)test();
}

Test details

Test 1

Verdict: ACCEPTED

input
3
4 4
1 2
3 4
1 2
...

correct output
-1
3
1

user output
-1
3
1

Test 2

Verdict:

input
10
15 200
1 14
2 6
3 14
...

correct output
-1
-1
-1
-1
-1
...

user output
1
1
1
1
1
...

Test 3

Verdict:

input
10
15 350
1 14
2 6
3 14
...

correct output
3
-1
2
-1
1
...

user output
1
1
1
1
1
...

Test 4

Verdict: ACCEPTED

input
10
15 1500
1 14
2 6
3 14
...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 5

Verdict:

input
10
15 100
4 10
3 9
6 15
...

correct output
-1
-1
-1
-1
-1
...

user output
1
1
1
1
1
...

Test 6

Verdict:

input
10
15 200
4 5
2 12
7 8
...

correct output
-1
-1
-1
-1
-1
...

user output
1
1
1
1
1
...

Test 7

Verdict:

input
10
15 300
5 10
6 12
12 13
...

correct output
-1
-1
2
2
-1
...

user output
1
1
1
1
1
...

Test 8

Verdict:

input
10
15 400
10 13
2 14
8 13
...

correct output
-1
1
1
-1
1
...

user output
1
1
1
1
1
...

Test 9

Verdict:

input
10
15 14
14 15
11 12
1 2
...

correct output
8
7
4
4
3
...

user output
8
4
4
3
2
...

Test 10

Verdict: ACCEPTED

input
10
15 14
1 2
2 3
3 4
...

correct output
14
7
5
4
3
...

user output
14
7
5
4
3
...