CSES - HIIT Open 2019 - Results
Submission details
Task:HIIT Speedrun
Sender:bigint bugaa
Submission time:2019-05-25 11:33:01 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.03 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.02 sdetails
#8ACCEPTED0.02 sdetails
#9ACCEPTED0.02 sdetails
#10ACCEPTED0.02 sdetails
#11ACCEPTED0.02 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.02 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int qi = 0; qi < q.size(); ++qi) {
                   ~~~^~~~~~~~~~

Code

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

struct X {
	int i;
	bool Hg, Tg;
	int Iw;
	int dst;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	string cs;
	cin >> cs;
	vector<int> v[n];
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int mdist[n][2][2][n+2];
	for (int i = 0; i < n; ++i)
	for (int Hi = 0; Hi < 2; ++Hi)
	for (int Ti = 0; Ti < 2; ++Ti)
	for (int Ii = 0; Ii < n+2; ++Ii) {
		mdist[i][Hi][Ti][Ii] = 1e9;
	}
	vector<X> q;
	q.push_back({0, 0, 0, n, 0});
	mdist[0][0][0][n] = 0;
	int res = 1e9;
	for (int qi = 0; qi < q.size(); ++qi) {
		X h = q[qi];
		if (cs[h.i] == 'H')
			h.Hg = 1;
		if (cs[h.i] == 'T')
			h.Tg = 1;
		if (cs[h.i] == 'I') {
			if (h.Iw < n && h.Iw != h.i)
				h.Iw = n+1;
			else if (h.Iw == n)
				h.Iw = h.i;
		}
		if (h.Hg && h.Tg && h.Iw == n+1 && h.i == n-1) {
			res = h.dst;
			break;
		}
		mdist[h.i][h.Hg][h.Tg][h.Iw] = h.dst;
		for (int j : v[h.i]) {
			int ncst = h.dst+1;
			if (ncst < mdist[j][h.Hg][h.Tg][h.Iw]) {
				mdist[j][h.Hg][h.Tg][h.Iw] = ncst;
				q.push_back({j, h.Hg, h.Tg, h.Iw, ncst});
			}
		}
	}
	if (res == 1e9) cout << "IMPOSSIBLE\n";
	else cout << res << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
4 0
HIIT

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 2

Verdict: ACCEPTED

input
4 3
HIIT
1 2
2 3
3 4

correct output
3

user output
3

Test 3

Verdict: ACCEPTED

input
4 3
HIIT
4 3
3 2
2 1

correct output
3

user output
3

Test 4

Verdict: ACCEPTED

input
6 5
XHIITX
1 2
1 3
1 4
...

correct output
9

user output
9

Test 5

Verdict: ACCEPTED

input
100 5000
TIIIIIIITHHHTHHHIHIIHIHHHITHIH...

correct output
3

user output
3

Test 6

Verdict: ACCEPTED

input
100 99
HIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
99

user output
99

Test 7

Verdict: ACCEPTED

input
10 10
AAAHIITAAA
1 2
2 3
3 4
...

correct output
9

user output
9

Test 8

Verdict: ACCEPTED

input
9 9
HIIIIIIIT
1 2
2 3
3 4
...

correct output
4

user output
4

Test 9

Verdict: ACCEPTED

input
9 9
HIIIIAAAT
1 2
2 3
3 4
...

correct output
5

user output
5

Test 10

Verdict: ACCEPTED

input
100 99
HIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
197

user output
197

Test 11

Verdict: ACCEPTED

input
8 8
HIITHIIT
1 2
2 3
3 4
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 12

Verdict: ACCEPTED

input
6 5
HIIITI
1 2
2 3
3 4
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 13

Verdict: ACCEPTED

input
100 99
HHHHHHHHHHHHHHHHHHHHHHHHHIIIII...

correct output
99

user output
99