답안 #126345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126345	2019-07-07T12:28:39 Z	eriksuenderhauf	007 (CEOI14_007)	C++11	0 / 100	398 ms	49272 KB

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int n, m, dp[4][MAXN];
vi adj[MAXN];

pii bfs(int src, int x, int y, int p) {
	deque<int> pq;
	mem(dp[p], 0x3f);
	dp[p][src] = 0;
	pq.pb(src);
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		for (int v: adj[u]) {
			if (dp[p][v] != 1061109567)
				continue;
			dp[p][v] = dp[p][u] + 1;
			pq.pb(v);
		}
	}
	return mp(dp[p][x], dp[p][y]);
}

int main() {
	int s, d, a, b;
	scanf("%d %d %d %d %d %d", &n, &m, &s, &d, &a, &b);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	pii a1 = bfs(s, a, b, 0);
	pii a2 = bfs(d, a, b, 1);
	pii a3 = bfs(a, a, b, 2);
	pii a4 = bfs(b, a, b, 3);
	//cerr << a1.fi << "/" << a2.fi << " | " << a1.se << "/" << a2.se << "\n";
	int ans = min(a2.fi - a1.fi, a2.se - a1.se);
	if (a2.fi == a2.se && a1.fi == a2.fi) {
		return -1;
		int mi = INF, i1 = 1;
		for (int i = 1; i <= n; i++) {
			if (dp[2][i] != dp[3][i])
				continue;
			if (dp[2][i] + dp[1][i] != a2.fi)
				continue;
			cerr << i << " " << dp[2][i] << " " << dp[1][i] << " " << dp[0][i] << "\n";
			if (mi > dp[2][i])
				i1 = i;
			mi = min(mi, dp[2][i]);
		}
		mi = INF, i1 = 1;
		for (int i = 1; i <= n; i++) {
			if (dp[2][i] != dp[3][i])
				continue;
			if (dp[2][i] + dp[0][i] != a1.fi)
				continue;
			cerr << i << " " << dp[2][i] << " " << dp[1][i] << " " << dp[0][i] << "\n";
			if (mi > dp[2][i])
				i1 = i;
			mi = min(mi, dp[2][i]);
		}
	}
	
	if (ans < 0) ans = -1;
	pri(ans);
    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:74:17: warning: variable 'i1' set but not used [-Wunused-but-set-variable]
   int mi = INF, i1 = 1;
                 ^~
007.cpp:68:6: warning: variable 'a3' set but not used [-Wunused-but-set-variable]
  pii a3 = bfs(a, a, b, 2);
      ^~
007.cpp:69:6: warning: variable 'a4' set but not used [-Wunused-but-set-variable]
  pii a4 = bfs(b, a, b, 3);
      ^~
007.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d", &n, &m, &s, &d, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	37 ms	39416 KB	Execution failed because the return code was nonzero
2	Correct	37 ms	39388 KB	Output is correct
3	Runtime error	36 ms	39464 KB	Execution failed because the return code was nonzero
4	Incorrect	37 ms	39544 KB	Output isn't correct
5	Incorrect	36 ms	39416 KB	Output isn't correct
6	Correct	37 ms	39416 KB	Output is correct
7	Correct	36 ms	39388 KB	Output is correct
8	Incorrect	37 ms	39416 KB	Output isn't correct
9	Correct	36 ms	39416 KB	Output is correct
10	Correct	36 ms	39416 KB	Output is correct
11	Correct	36 ms	39416 KB	Output is correct
12	Incorrect	36 ms	39420 KB	Output isn't correct
13	Correct	36 ms	39416 KB	Output is correct
14	Incorrect	37 ms	39416 KB	Output isn't correct
15	Correct	36 ms	39416 KB	Output is correct
16	Incorrect	37 ms	39444 KB	Output isn't correct
17	Incorrect	37 ms	39416 KB	Output isn't correct
18	Incorrect	36 ms	39516 KB	Output isn't correct
19	Correct	37 ms	39512 KB	Output is correct
20	Correct	37 ms	39544 KB	Output is correct
21	Correct	36 ms	39516 KB	Output is correct
22	Correct	37 ms	39544 KB	Output is correct
23	Correct	37 ms	39544 KB	Output is correct
24	Incorrect	37 ms	39544 KB	Output isn't correct

Subtask #2
0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	40696 KB	Output is correct
2	Incorrect	86 ms	41328 KB	Output isn't correct
3	Correct	70 ms	40824 KB	Output is correct
4	Incorrect	84 ms	41464 KB	Output isn't correct
5	Correct	67 ms	40696 KB	Output is correct
6	Correct	70 ms	40824 KB	Output is correct
7	Correct	75 ms	40952 KB	Output is correct
8	Correct	79 ms	40988 KB	Output is correct
9	Incorrect	88 ms	41464 KB	Output isn't correct
10	Correct	233 ms	45688 KB	Output is correct
11	Incorrect	111 ms	42232 KB	Output isn't correct
12	Correct	141 ms	43100 KB	Output is correct
13	Incorrect	122 ms	42488 KB	Output isn't correct
14	Correct	100 ms	41976 KB	Output is correct
15	Correct	146 ms	43128 KB	Output is correct
16	Correct	138 ms	43296 KB	Output is correct
17	Correct	134 ms	42872 KB	Output is correct
18	Incorrect	133 ms	42872 KB	Output isn't correct
19	Correct	228 ms	44024 KB	Output is correct
20	Incorrect	355 ms	46792 KB	Output isn't correct
21	Incorrect	200 ms	44588 KB	Output isn't correct
22	Correct	166 ms	43784 KB	Output is correct
23	Correct	300 ms	44568 KB	Output is correct
24	Correct	218 ms	44416 KB	Output is correct
25	Incorrect	217 ms	44152 KB	Output isn't correct
26	Correct	187 ms	43960 KB	Output is correct
27	Correct	217 ms	44528 KB	Output is correct
28	Correct	208 ms	44432 KB	Output is correct
29	Correct	251 ms	45404 KB	Output is correct
30	Incorrect	325 ms	47304 KB	Output isn't correct
31	Incorrect	243 ms	45304 KB	Output isn't correct
32	Correct	194 ms	44536 KB	Output is correct
33	Correct	187 ms	44664 KB	Output is correct
34	Incorrect	217 ms	44996 KB	Output isn't correct
35	Incorrect	203 ms	44664 KB	Output isn't correct
36	Incorrect	230 ms	45000 KB	Output isn't correct
37	Correct	250 ms	45560 KB	Output is correct
38	Correct	260 ms	45432 KB	Output is correct
39	Correct	340 ms	45432 KB	Output is correct
40	Incorrect	312 ms	47112 KB	Output isn't correct
41	Correct	398 ms	49272 KB	Output is correct

답안 #126345

Compilation message

Subtask #1 0.0 / 30.0

Subtask #2 0.0 / 70.0

Subtask #1
0.0 / 30.0

Subtask #2
0.0 / 70.0