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

Code

#include <iostream>
#include <vector>
#include <deque>

using namespace std;
typedef long long LL;

#define foxnews cin
#define twitter cout

string labels;
LL n, m; 

bool is_hiit(vector<LL>& nodes){
    bool has_H = false;
    bool has_T = false;
    bool has_II = false;
    LL I_pos = -1;        
    
    for(LL v : nodes){
        if(labels[v] == 'H') has_H = true;
        if(labels[v] == 'T') has_T = true;
        if(labels[v] == 'I'){
            if(I_pos != -1 && v != I_pos) has_II = true;
            I_pos = v;
        }
    }

    return has_H && has_II && has_T;

}

void bfs(LL start, vector<vector<LL> >& D, vector<vector<LL> >& M){
    vector<bool> visited(n, false);
    deque<pair<LL, LL> > mexicans;
    mexicans.push_front({start,0});
    while(!mexicans.empty()){
        auto P = mexicans.back(); mexicans.pop_back();
        LL v = P.first;
        LL d = P.second;
        if(visited[v]) continue;
        visited[v] = true;
        D[start][v] = d;
        for(LL u = 0; u < n; u++){
            if(M[v][u]) mexicans.push_front({u,d+1});
        }
    }
}

int main(){
    foxnews >> n >> m;
    foxnews >> labels;

    vector<vector<LL > > M(n, vector<LL>(n)); // neighbors
    for(LL i = 0; i < m; i++){
        LL u,v; foxnews >> u >> v;
        u--; v--;
        M[u][v] = 1;
        M[v][u] = 1;
    }

    vector<vector<LL > > D(n, vector<LL>(n,1e9));

    for(LL v = 0; v < n; v++) bfs(v, D, M);    

/*
    for(LL u = 0; u < n; u++) D[u][u] = 0;
    for(LL u = 0; u < n; u++) for(LL v = 0; v < n; v++) if(M[u][v] == 1) {
        D[u][v] = 1;
        D[v][u] = 1;
    }

    for(LL u = 0; u < n; u++){ // start
        for(LL w = 0; w < n; w++){ // end
            for(LL v = 0; v < n; v++){ // middle
                if(M[u][v] == 1 && M[v][w] == 1)
                    D[u][w] = min(D[u][w], D[u][v] + D[v][w]);
            }
        }
    }
*/
/*
    for(LL u = 0; u < n; u++){ // start
        for(LL w = 0; w < n; w++){ // end
            cout << u << " " << w << " " << D[u][w] << endl;
        }
    }
*/

    LL ans = 1e9;

    vector<LL> nodes(6);
    for(LL v1 = 0; v1 < n; v1++){
        for(LL v2 = 0; v2 < n; v2++){
            for(LL v3 = 0; v3 < n; v3++){
                for(LL v4 = 0; v4 < n; v4++){
                    nodes[0] = v1; nodes[1] = v2, nodes[2] = v3; nodes[3] = v4; nodes[4] = 0; nodes[5] = n-1;
                    if(is_hiit(nodes)){
                        ans = min(ans,D[0][v1] + D[v1][v2] + D[v2][v3] + D[v3][v4] + D[v4][n-1]); 
                    }
                }
            }
        }
    }

    if(ans == (LL)1e9){
        twitter << "IMPOSSIBLE" << endl;
    } else twitter << ans << 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:

input
100 5000
TIIIIIIITHHHTHHHIHIIHIHHHITHIH...

correct output
3

user output
(empty)

Test 6

Verdict:

input
100 99
HIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
99

user output
(empty)

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:

input
100 99
HIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
197

user output
(empty)

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:

input
100 99
HHHHHHHHHHHHHHHHHHHHHHHHHIIIII...

correct output
99

user output
(empty)