HIIT Speedrun

#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});
        }
    }
}
 
#define LI 0x1
#define LH 0x10
#define LT 0x100
 
int main(){
    foxnews >> n >> m;
    foxnews >> labels;
 
    vector<LL> lb;
 
    for(char ch : labels) {
      switch(ch) {
      case 'H': lb.push_back(LH); break;
      case 'I': lb.push_back(LI); break;
      case 'T': lb.push_back(LT); break;
      default: lb.push_back(0);
      }
    }
 
    LL base = lb[0] + lb.back();
 
    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);    
 
    LL ans = 1e9;
 
    for(LL v1 = 0; v1 < n; v1++){
        for(LL v2 = 0; v2 < n; v2++){
            if(v1 == v2) continue;
            for(LL v3 = 0; v3 < n; v3++){
                if(v3 == v1 || v3 == v2) continue;
                for(LL v4 = 0; v4 < n; v4++){
                    if(v4 == v1 || v4 == v2 || v4 == v3) continue;
                    int sum = lb[v1] + lb[v2] + lb[v3] + lb[v4] + base;
                    if((sum&0xF)>1 && (sum&0xF0) && (sum&0xF00)) {
                        ans = min(ans,D[0][v1] + D[v1][v2] + D[v2][v3] + D[v3][v4] + D[v4][n-1]); 
                    }
                }
            }
        }
    }
 
    for(LL v1 = 0; v1 < n; v1++){
        for(LL v2 = 0; v2 < n; v2++){
            if(v1 == v2) continue;
            for(LL v3 = 0; v3 < n; v3++){
                if(v3 == v1 || v3 == v2) continue;
                    int sum = lb[v1] + lb[v2] + lb[v3] + base;
                    if((sum&0xF)>1 && (sum&0xF0) && (sum&0xF00)) {
                        ans = min(ans,D[0][v1] + D[v1][v2] + D[v2][v3] + D[v3][n-1]); 
                    }
            }
        }
    }
 
    for(LL v1 = 0; v1 < n; v1++){
        for(LL v2 = 0; v2 < n; v2++){
            if(v1 == v2) continue;
                    LL sum = lb[v1] + lb[v2] + base;
                    if((sum&0xF)>1 && (sum&0xF0) && (sum&0xF00)) {
                        ans = min(ans,D[0][v1] + D[v1][v2] + D[v2][n-1]); 
                    }
            }
        }
 
    if(ans == (LL)1e9){
        twitter << "IMPOSSIBLE" << endl;
    } else twitter << ans << endl;
 
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED