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

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n, m;
const long long inf=1e18l;
long long sh[111][(101)<<4];
vector<int> rt[101010];
priority_queue<pair<pair<long long, int>, int> > pq;
char ch[111];
int main(){
cin >> n >> m;
cin >> ch;
for (int i=0;i<m;++i){
int a, b;
cin >> a >> b;
rt[a].push_back(b);
rt[b].push_back(a);
}
for (int i=0;i<111;++i) for (int j=0;j<((101)<<4);++j) sh[i][j]=inf;
sh[1][0]=0;
pq.push({{0,0},1});
bool ok=0;
long long ans=0;
while (!pq.empty()){
pair<pair<long long, int>, int> cp=pq.top();
pq.pop();
long long d=-cp.F.F;
int c=cp.S;
int t=cp.F.S;
if (sh[c][t]<d) continue;
if (ch[c-1]=='H'){
t|=1;
}else if (ch[c-1]=='I'){
if (~t&2){
t|=2|(c<<4);
}else if (t>>4 != c){
t|=4;
}
}else if (ch[c-1]=='T'){
t|=8;
}
// cout << c << ", " << d << ", " << t << endl;
if (c==n && (t&15)==15){
ok=1;
ans=d;
break;
}
for (auto w:rt[c]){
if (sh[w][t]<=d+1) continue;
sh[w][t]=d+1;
pq.push({{-d-1, t}, w});
}
}
if (ok) cout << ans << "\n";
else cout << "IMPOSSIBLE\n";
}

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