oj.uz

답안 #126347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126347 2019-07-07T12:30:34 Z eriksuenderhauf 007 (CEOI14_007) C++11
0 / 100
 1000 ms 49332 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 == a1.se) {
		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 (a2.fi == a2.se) while(1);
	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 Execution timed out 1086 ms 39416 KB Time limit exceeded
2 Correct 44 ms 39416 KB Output is correct
3 Runtime error 41 ms 39544 KB Execution failed because the return code was nonzero
4 Runtime error 43 ms 39544 KB Execution failed because the return code was nonzero
5 Runtime error 43 ms 39416 KB Execution failed because the return code was nonzero
6 Runtime error 36 ms 39416 KB Execution failed because the return code was nonzero
7 Runtime error 37 ms 39416 KB Execution failed because the return code was nonzero
8 Runtime error 36 ms 39376 KB Execution failed because the return code was nonzero
9 Runtime error 37 ms 39544 KB Execution failed because the return code was nonzero
10 Execution timed out 1080 ms 39416 KB Time limit exceeded
11 Correct 37 ms 39416 KB Output is correct
12 Runtime error 37 ms 39416 KB Execution failed because the return code was nonzero
13 Runtime error 36 ms 39544 KB Execution failed because the return code was nonzero
14 Runtime error 37 ms 39484 KB Execution failed because the return code was nonzero
15 Runtime error 36 ms 39416 KB Execution failed because the return code was nonzero
16 Runtime error 37 ms 39496 KB Execution failed because the return code was nonzero
17 Runtime error 37 ms 39416 KB Execution failed because the return code was nonzero
18 Runtime error 37 ms 39416 KB Execution failed because the return code was nonzero
19 Runtime error 36 ms 39416 KB Execution failed because the return code was nonzero
20 Runtime error 37 ms 39544 KB Execution failed because the return code was nonzero
21 Correct 37 ms 39544 KB Output is correct
22 Runtime error 37 ms 39544 KB Execution failed because the return code was nonzero
23 Runtime error 37 ms 39544 KB Execution failed because the return code was nonzero
24 Runtime error 37 ms 39436 KB Execution failed because the return code was nonzero

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 40656 KB Execution failed because the return code was nonzero
2 Runtime error 108 ms 41248 KB Execution failed because the return code was nonzero
3 Runtime error 92 ms 40824 KB Execution failed because the return code was nonzero
4 Runtime error 90 ms 41336 KB Execution failed because the return code was nonzero
5 Correct 69 ms 40696 KB Output is correct
6 Correct 73 ms 41000 KB Output is correct
7 Runtime error 77 ms 40952 KB Execution failed because the return code was nonzero
8 Runtime error 87 ms 40952 KB Execution failed because the return code was nonzero
9 Runtime error 91 ms 41336 KB Execution failed because the return code was nonzero
10 Runtime error 233 ms 45560 KB Execution failed because the return code was nonzero
11 Runtime error 128 ms 42372 KB Execution failed because the return code was nonzero
12 Runtime error 145 ms 42964 KB Execution failed because the return code was nonzero
13 Runtime error 185 ms 42552 KB Execution failed because the return code was nonzero
14 Runtime error 122 ms 42076 KB Execution failed because the return code was nonzero
15 Runtime error 155 ms 43008 KB Execution failed because the return code was nonzero
16 Correct 161 ms 43352 KB Output is correct
17 Runtime error 141 ms 42852 KB Execution failed because the return code was nonzero
18 Runtime error 150 ms 42916 KB Execution failed because the return code was nonzero
19 Runtime error 173 ms 44024 KB Execution failed because the return code was nonzero
20 Runtime error 292 ms 46960 KB Execution failed because the return code was nonzero
21 Runtime error 211 ms 44408 KB Execution failed because the return code was nonzero
22 Runtime error 183 ms 43804 KB Execution failed because the return code was nonzero
23 Correct 202 ms 44616 KB Output is correct
24 Runtime error 192 ms 44408 KB Execution failed because the return code was nonzero
25 Runtime error 193 ms 44028 KB Execution failed because the return code was nonzero
26 Correct 160 ms 43896 KB Output is correct
27 Runtime error 199 ms 44408 KB Execution failed because the return code was nonzero
28 Runtime error 230 ms 44508 KB Execution failed because the return code was nonzero
29 Runtime error 220 ms 45304 KB Execution failed because the return code was nonzero
30 Runtime error 295 ms 47352 KB Execution failed because the return code was nonzero
31 Runtime error 229 ms 45404 KB Execution failed because the return code was nonzero
32 Runtime error 215 ms 44408 KB Execution failed because the return code was nonzero
33 Correct 198 ms 44664 KB Output is correct
34 Runtime error 237 ms 44880 KB Execution failed because the return code was nonzero
35 Runtime error 251 ms 44792 KB Execution failed because the return code was nonzero
36 Runtime error 215 ms 44792 KB Execution failed because the return code was nonzero
37 Correct 264 ms 45688 KB Output is correct
38 Runtime error 275 ms 45432 KB Execution failed because the return code was nonzero
39 Runtime error 287 ms 45432 KB Execution failed because the return code was nonzero
40 Runtime error 313 ms 47096 KB Execution failed because the return code was nonzero
41 Runtime error 412 ms 49332 KB Execution failed because the return code was nonzero