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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:53:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < connections[p].size(); j++) {
                             ~~^~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int h_i = 0; h_i < hs.size(); h_i++) {
                       ~~~~^~~~~~~~~~~
input/code.cpp:72:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i1_i = 0; i1_i < is.size(); i1_i++) {
                            ~~~~~^~~~~~~~~~~
input/code.cpp:74:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i2_i = i1_i+1; i2_i < is.size(); i2_i++) {
                                     ~~~~~^~~~~~~~~~~
input/code.cpp:76:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compar

Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> hs;
vector<int> is;
vector<int> ts;
vector<int> connections[100];

int distances[100][100] = {0};

unsigned min(unsigned a, unsigned b) {
    return a < b ? a : b;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'H'){
            hs.push_back(i);
        }
        if (c == 'I'){
            is.push_back(i);
        }
        if (c == 'T'){
            ts.push_back(i);
        }
    }
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        connections[a-1].push_back(b-1);
        connections[b-1].push_back(a-1);
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            distances[i][j] = -1;
        }
        distances[i][i] = 0;
        
        queue<int> q;
        q.push(i);
        while (q.size()) {
            int p = q.front();
            q.pop();
            for (int j = 0; j < connections[p].size(); j++) {
                int neigh = connections[p][j];
                if (distances[i][neigh] == -1) {
                    distances[i][neigh] = distances[i][p] + 1;
                    q.push(neigh);
                }
            }
        }
    }

    unsigned shortest = -1;
    
#define TRYM(a, b, c, d) \
    if (distances[0][a] != -1 && distances[a][b] != -1 && distances[b][c] != -1 && distances[c][d] != -1 && distances[d][n-1] != -1) { \
    shortest = min(shortest, distances[0][a] + distances[a][b] + distances[b][c] + distances[c][d] + distances[d][n-1]); \
    }

    for (int h_i = 0; h_i < hs.size(); h_i++) {
        int h = hs[h_i];
        for (int i1_i = 0; i1_i < is.size(); i1_i++) {
            int i1 = is[i1_i];
            for (int i2_i = i1_i+1; i2_i < is.size(); i2_i++) {
                int i2 = is[i2_i];
                for (int t_i = 0; t_i < ts.size(); t_i++) {
                    int t = ts[t_i];
                    TRYM(h, i1, i2, t);
                    TRYM(h, i1, t, i2);
                    TRYM(h, i2, i1, t);
                    TRYM(h, i2, t, i1);
                    TRYM(h, t, i1, i2);
                    TRYM(h, t, i2, i1);

                    TRYM(i1, h, i2, t);
                    TRYM(i1, h, t, i2);
                    TRYM(i1, i2, h, t);
                    TRYM(i1, i2, t, h);
                    TRYM(i1, t, h, i2);
                    TRYM(i1, t, i2, h);
                    
                    TRYM(i2, i1, h, t);
                    TRYM(i2, i1, t, h);
                    TRYM(i2, h, i1, t);
                    TRYM(i2, h, t, i1);
                    TRYM(i2, t, i1, h);
                    TRYM(i2, t, h, i1);
                    
                    TRYM(t, i1, i2, h);
                    TRYM(t, i1, h, i2);
                    TRYM(t, i2, i1, h);
                    TRYM(t, i2, h, i1);
                    TRYM(t, h, i1, i2);
                    TRYM(t, h, i2, i1);
                }
            }
        }
    }
    
    if (shortest == (unsigned) -1) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << shortest << 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