oj.uz

Submission #429711

# Submission time Handle Problem Language Result Execution time Memory
429711 2021-06-16T08:54:15 Z 최서현(#7502) Brackets (CPSPC17_brackets) C++17
0 / 100
 7 ms 1036 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];

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;

    priority_queue<piii, vector<piii>, greater<piii>> Q;
    for(int i = 0; i < n; ++i) Q.push({0, {i, i}});
    while(Q.size())
    {
        auto x = Q.top(); Q.pop();
        if(C[x.ee][x.rr] != INF) continue;
        C[x.ee][x.rr] = x.ff;
        for(int i = 0; i < 8; i += 2)
            for(auto j : rgph[x.ee][i])
                for(auto k : gph[x.rr][i + 1])
                    Q.push({x.ff + 2, {j, k}});
        for(int i = 0; i < n; ++i)
        {
            if(C[i][x.rr] > C[x.ee][x.rr] + C[i][x.ee])
                C[i][x.rr] = C[x.ee][x.rr] + C[i][x.ee], Q.push({C[i][x.rr], {i, x.rr}});
            if(C[x.ee][i] > C[x.ee][x.rr] + C[x.rr][i])
                C[x.ee][i] = C[x.ee][x.rr] + C[x.rr][i], Q.push({C[x.ee][i], {x.ee, 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:28:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         int z;
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -