oj.uz

Submission #429528

# Submission time Handle Problem Language Result Execution time Memory
429528 2021-06-16T05:36:13 Z 송준혁(#7525) Brackets (CPSPC17_brackets) C++17
26 / 100
 60 ms 17452 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], Q[40404], adj[220][220];

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++) Q[0].pb(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));
	for (int d=0; d<=N*N; d++){
		for (pii u : Q[d]){
			if (u.fi == S && u.se == T){
				printf("%d\n", 2*d);
				return 0;
			}
			if (D[u.fi][u.se] != MOD) continue;
			D[u.fi][u.se] = d;
			for (pii v : adj[u.fi][u.se]) Q[d+1].pb(v);
			for (int i=1; i<=N; i++){
				if (D[i][u.fi] + d <= N*N && i != u.fi) Q[D[i][u.fi] + d].pb(pii(i, u.se));
				if (D[u.se][i] + d <= N*N && i != u.se) Q[D[u.se][i] + d].pb(pii(u.fi, i));
			}
		}
	}
	puts("-1");
	return 0;
}

Compilation message

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Correct 2 ms 2380 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 2 ms 2380 KB Output is correct
6 Correct 2 ms 2380 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2380 KB Output is correct
10 Correct 2 ms 2380 KB Output is correct
11 Correct 2 ms 2380 KB Output is correct
12 Correct 2 ms 2380 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Correct 2 ms 2380 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 2 ms 2380 KB Output is correct
6 Correct 2 ms 2380 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2380 KB Output is correct
10 Correct 2 ms 2380 KB Output is correct
11 Correct 2 ms 2380 KB Output is correct
12 Correct 2 ms 2380 KB Output is correct
13 Correct 2 ms 2380 KB Output is correct
14 Correct 2 ms 2380 KB Output is correct
15 Correct 2 ms 2380 KB Output is correct
16 Correct 2 ms 2380 KB Output is correct
17 Correct 2 ms 2380 KB Output is correct
18 Correct 2 ms 2380 KB Output is correct
19 Incorrect 3 ms 2380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Correct 2 ms 2380 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 2 ms 2380 KB Output is correct
6 Correct 2 ms 2380 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2380 KB Output is correct
10 Correct 2 ms 2380 KB Output is correct
11 Correct 2 ms 2380 KB Output is correct
12 Correct 2 ms 2380 KB Output is correct
13 Correct 2 ms 2380 KB Output is correct
14 Correct 2 ms 2380 KB Output is correct
15 Correct 2 ms 2380 KB Output is correct
16 Correct 2 ms 2380 KB Output is correct
17 Correct 2 ms 2380 KB Output is correct
18 Correct 2 ms 2380 KB Output is correct
19 Incorrect 3 ms 2380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Correct 2 ms 2380 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 2 ms 2380 KB Output is correct
6 Correct 2 ms 2380 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2380 KB Output is correct
10 Correct 2 ms 2380 KB Output is correct
11 Correct 2 ms 2380 KB Output is correct
12 Correct 2 ms 2380 KB Output is correct
13 Correct 2 ms 2380 KB Output is correct
14 Correct 2 ms 2380 KB Output is correct
15 Correct 2 ms 2380 KB Output is correct
16 Correct 2 ms 2380 KB Output is correct
17 Correct 2 ms 2380 KB Output is correct
18 Correct 2 ms 2380 KB Output is correct
19 Incorrect 3 ms 2380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 16824 KB Output is correct
2 Correct 47 ms 17452 KB Output is correct
3 Correct 48 ms 16676 KB Output is correct
4 Correct 57 ms 16516 KB Output is correct
5 Correct 49 ms 16552 KB Output is correct
6 Correct 47 ms 16168 KB Output is correct
7 Correct 49 ms 16500 KB Output is correct
8 Correct 60 ms 16800 KB Output is correct
9 Correct 45 ms 16468 KB Output is correct
10 Correct 45 ms 15868 KB Output is correct
11 Correct 44 ms 15928 KB Output is correct
12 Correct 46 ms 15916 KB Output is correct
13 Correct 41 ms 15648 KB Output is correct
14 Correct 14 ms 5708 KB Output is correct
15 Correct 16 ms 5864 KB Output is correct
16 Correct 3 ms 2508 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2380 KB Output is correct
2 Correct 2 ms 2380 KB Output is correct
3 Correct 2 ms 2380 KB Output is correct
4 Correct 2 ms 2380 KB Output is correct
5 Correct 2 ms 2380 KB Output is correct
6 Correct 2 ms 2380 KB Output is correct
7 Correct 2 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 2 ms 2380 KB Output is correct
10 Correct 2 ms 2380 KB Output is correct
11 Correct 2 ms 2380 KB Output is correct
12 Correct 2 ms 2380 KB Output is correct
13 Correct 2 ms 2380 KB Output is correct
14 Correct 2 ms 2380 KB Output is correct
15 Correct 2 ms 2380 KB Output is correct
16 Correct 2 ms 2380 KB Output is correct
17 Correct 2 ms 2380 KB Output is correct
18 Correct 2 ms 2380 KB Output is correct
19 Incorrect 3 ms 2380 KB Output isn't correct
20 Halted 0 ms 0 KB -