CSES - HIIT Open 2018 - Results
Submission details
Task:Monotonic
Sender:Karhukopla
Submission time:2018-05-26 13:59:11 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#30.01 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails

Code

#include <bits/stdc++.h>

#define ll long long
#define lll __int128
#define pii pair<int, int>
#define M 1000000007
#define N 101
#define PB push_back
#define F first
#define S second
using namespace std;

int e[20][20];

int solve() {
	int n, m;
	cin>>n>>m;
	pii p[m];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			e[i][j] = n * n;
		}
		e[i][i] = 0;
	}
	
	for (int i = 0; i < m; i++) {
		cin>>p[i].F>>p[i].S;
		p[i].F--;
		p[i].S--;
		e[p[i].F][p[i].S] = 1;
	}
	int ans = 0;
	
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (e[i][j] == n * n) return -1;
			ans = max(ans, e[i][j]);
		}
	}
	return ans;
}

int main () {
	srand(time(0));
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll t; cin >> t;
	while(t--) cout << solve() << "\n";
}

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: ACCEPTED

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
2
-1
2
-1
2
...

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: ACCEPTED

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: ACCEPTED

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: ACCEPTED

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

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

user output
-1
-1
2
2
-1
...

Test 8

Verdict:

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

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

user output
-1
2
2
-1
2
...

Test 9

Verdict:

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

correct output
8
7
4
4
3
...

user output
14
14
14
14
14
...

Test 10

Verdict:

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

correct output
14
7
5
4
3
...

user output
14
14
14
14
14
...