oj.uz

Submission #429523

# Submission time Handle Problem Language Result Execution time Memory
429523 2021-06-16T05:15:31 Z 송준혁(#7525) Brackets (CPSPC17_brackets) C++17
0 / 100
 27 ms 5040 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];
vector<pii> V[8], adj[220][220];
queue<pii> Q;

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++) D[i][i] = 0, Q.push(pii(i,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(pii(a.se, b.se));
	while (Q.size()){
		pii u = Q.front(); Q.pop();
		for (pii v : adj[u.fi][u.se]){
			if (D[v.fi][v.se] == MOD){
				D[v.fi][v.se] = D[u.fi][u.se]+1;
				Q.push(v);
			}
		}
	}
	for (int i=1; i<=N; i++) D[i][i] = MOD;
	for (int k=1; k<=N; k++) for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
	if (D[S][T] == MOD) puts("-1");
	else printf("%d\n", 2*D[S][T]);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d %d %d %d", &N, &M, &S, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:22:8: 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 Correct 2 ms 1356 KB Output is correct
2 Incorrect 1 ms 1356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 26.0

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