oj.uz

Submission #429545

# Submission time Handle Problem Language Result Execution time Memory
429545 2021-06-16T05:58:22 Z 송준혁(#7525) Brackets (CPSPC17_brackets) C++17
0 / 100
 36 ms 3884 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, S, T;
int D[220][220];
bool vis[220][220];
vector<pii> V[8];
vector<int> adj[220][220];
priority_queue<pii> PQ;

int main(){
	char c;
	scanf("%d %d %d %d", &N, &M, &S, &T);
	for (int i=1; i<=M; i++){
		int u, v;
		scanf("%d %d %c", &u, &v, &c);
		if (c == '(') V[0].pb(pii(v, u));
		if (c == '{') V[1].pb(pii(v, u));
		if (c == '[') V[2].pb(pii(v, u));
		if (c == '<') V[3].pb(pii(v, u));
		if (c == ')') V[4].pb(pii(u, v));
		if (c == '}') V[5].pb(pii(u, v));
		if (c == ']') V[6].pb(pii(u, v));
		if (c == '>') V[7].pb(pii(u, v));
	}
	for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) D[i][j] = MOD;
	for (int i=1; i<=N; i++) PQ.push(pii(0, i*(N+1)+i));
	for (int i=0; i<4; i++) for (pii a : V[i]) for (pii b : V[i+4]) adj[a.fi][b.fi].pb(a.se*(N+1)+b.se);
	while (PQ.size()){
		int d = -PQ.top().fi;
		int a = PQ.top().se/(N+1);
		int b = PQ.top().se%(N+1);
		PQ.pop();

		if (a == S && b == T){
			printf("%d\n", 2*d);
			return 0;
		}
		if (vis[a][b]) continue;
		vis[a][b] = true;
		for (int v : adj[a][b]) PQ.push(pii(-d-1, v));
		for (int i=1; i<=N; i++){
			if (D[i][b] > D[i][a] + d) D[i][b] = D[i][a] + d, PQ.push(pii(-D[i][a]-d, i*(N+1) + b));
			if (D[a][i] > D[b][i] + d) D[a][i] = D[b][i] + d, PQ.push(pii(-D[b][i]-d, a*(N+1) + i));
		}
	}
	puts("-1");
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d %d %d %d", &N, &M, &S, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d %d %c", &u, &v, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 26.0

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