oj.uz

Submission #429551

# Submission time Handle Problem Language Result Execution time Memory
429551 2021-06-16T06:26:54 Z 조영욱(#7653) Brackets (CPSPC17_brackets) C++17
0 / 100
 71 ms 3364 KB 
#include <bits/stdc++.h>
using namespace std;

char str[8]={'(','{','[','<','>',']','}',')'};
bool vis[200][200][5];
long long dist[200][200][5];
int arr[200][200];
int n,m;
const long long INF=2e18;
typedef pair<long long,long long> P;
typedef pair<P,P> PP;
typedef pair<P,int> Pi;

int main(void) {
    int s,t;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    s--;
    t--;
    for(int i=0;i<m;i++) {
        int u,v;
        char c;
        scanf("%d %d %c",&u,&v,&c);
        u--;
        v--;
        int val=-1;
        for(int j=0;j<8;j++) {
            if (str[j]==c){
                val=j;
                break;
            }
        }
        if (val!=-1)
        arr[u][v]|=(1<<val);
    }
    priority_queue<PP,vector<PP>,greater<PP>> pq;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            for(int k=0;k<5;k++) {
                if (i==j&&k==4) {
                    dist[i][j][k]=0;
                    pq.push(PP(P(0,k),P(i,j)));
                }
                else {
                    dist[i][j][k]=INF;
                }
            }
        }
    }
    while (!pq.empty()) {
        Pi now;
        do {
            now=Pi(pq.top().second,pq.top().first.second);
            pq.pop();
        } while (!pq.empty()&&vis[now.first.first][now.first.second][now.second]);
        int xpos=now.first.first;
        int ypos=now.first.second;
        int type=now.second;
        if (vis[xpos][ypos][type]) {
            break;
        }
        vis[xpos][ypos][type]=true;
        if (now.second==4) {
            for(int i=0;i<n;i++) {
                for(int k=0;k<4;k++) {
                    if ((arr[i][xpos]&(1<<k))) {
                        if (dist[xpos][ypos][type]+1<dist[i][ypos][k]) {
                            dist[i][ypos][k]=dist[xpos][ypos][type]+1;
                            pq.push(PP(P(dist[i][ypos][k],k),P(i,ypos)));
                        }
                    }
                }
            }
            for(int i=0;i<n;i++) {
                if (dist[xpos][ypos][4]+dist[ypos][i][4]<dist[xpos][i][4]) {
                    dist[xpos][i][4]=dist[xpos][ypos][4]+dist[ypos][i][4];
                    pq.push(PP(P(dist[xpos][i][4],4),P(xpos,i)));
                }
            }
        }
        else {
            for(int i=0;i<n;i++) {
                if (arr[ypos][i]&(1<<(7-type))) {
                    if (dist[xpos][ypos][type]+1<dist[xpos][i][4]) {
                        dist[xpos][i][4]=dist[xpos][ypos][type]+1;
                        pq.push(PP(P(dist[xpos][i][4],4),P(xpos,i)));
                    }
                }
            }
        }
    }
    printf("%lld\n",dist[s][t][4]>INF/2?-1:dist[s][t][4]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d %d %d",&n,&m,&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d %d %c",&u,&v,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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 71 ms 3364 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 -