oj.uz

Submission #430176

# Submission time Handle Problem Language Result Execution time Memory
430176 2021-06-16T11:53:06 Z 최서현(#7488) Brackets (CPSPC17_brackets) C++17
0 / 100
 168 ms 193420 KB 
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define piii pair<int, pii>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

const int INF = (int)1e9 + 7;
vector<int> gph[202][8];
vector<int> rgph[202][8];
vector<pii> Q[4040404];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int n, m, s, e; cin >> n >> m >> s >> e; --s; --e;
    for(int i = 0; i < m; ++i)
    {
        int x, y; char c; cin >> x >> y >> c; --x; --y;
        int z;
        if(c == '<') z = 0;
        if(c == '>') z = 1;
        if(c == '{') z = 2;
        if(c == '}') z = 3;
        if(c == '[') z = 4;
        if(c == ']') z = 5;
        if(c == '(') z = 6;
        if(c == ')') z = 7;
        gph[x][z].push_back(y);
        rgph[y][z].push_back(x);
    }

    int C[n][n];
    for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) C[i][j] = INF;
    for(int i = 0; i < n; ++i) Q[0].push_back({i, i});

    for(int d = 0; d < 4040404; d += 2)
    {
        for(auto x : Q[d])
        {
            if(C[x.ff][x.ss] != INF) continue;
            C[x.ff][x.ss] = d;
            for(int i = 0; i < 8; i += 2)
                for(auto j : rgph[x.ff][i])
                    for(auto k : gph[x.ss][i + 1])
                        if(C[j][k] == INF)
                            Q[d + 2].push_back({j, k});
            for(int i = 0; i < n; ++i)
            {
                if(C[i][x.ss] == INF)
                    Q[C[x.ff][x.ss] + C[i][x.ff]].push_back({i, x.ss});
                if(C[x.ff][i] == INF)
                    Q[C[x.ff][x.ss] + C[x.ss][i]].push_back({x.ff, i});
            }
        }
    }

//    for(int i = 0; i < n; ++i)
//    {
//        for(int j = 0; j < n; ++j)
//            cout << C[i][j] << ' ';
//        cout << endl;
//    }

    cout << (C[s][e] == INF ? -1 : C[s][e]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:29:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         int z;
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 192968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 192968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 192968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 192968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 193420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 192968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -