oj.uz

답안 #126340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126340 2019-07-07T12:23:32 Z eriksuenderhauf 007 (CEOI14_007) C++11
0 / 100
 427 ms 49400 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) {
		int mi = INF, ind = 1;
		for (int i = 1; i <= n; i++) {
			if (dp[2][i] != dp[3][i])
				continue;
			if (mi > dp[2][i])
				ind = i;
			mi = min(mi, dp[2][i]);
		}
		if (dp[0][ind] <= dp[1][ind])
			ans--;
	}
	
	if (ans < 0) ans = -1;
	pri(ans);
    return 0;
}

Compilation message

007.cpp: In function 'int main()':
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 Correct 36 ms 39416 KB Output is correct
2 Correct 36 ms 39416 KB Output is correct
3 Correct 37 ms 39452 KB Output is correct
4 Incorrect 36 ms 39416 KB Output isn't correct
5 Incorrect 36 ms 39416 KB Output isn't correct
6 Partially correct 36 ms 39416 KB Partially correct
7 Correct 36 ms 39416 KB Output is correct
8 Incorrect 36 ms 39416 KB Output isn't correct
9 Partially correct 37 ms 39416 KB Partially correct
10 Partially correct 36 ms 39416 KB Partially correct
11 Correct 36 ms 39416 KB Output is correct
12 Incorrect 36 ms 39416 KB Output isn't correct
13 Partially correct 37 ms 39416 KB Partially correct
14 Incorrect 36 ms 39416 KB Output isn't correct
15 Partially correct 36 ms 39420 KB Partially correct
16 Correct 37 ms 39416 KB Output is correct
17 Incorrect 41 ms 39544 KB Output isn't correct
18 Correct 36 ms 39416 KB Output is correct
19 Partially correct 36 ms 39444 KB Partially correct
20 Partially correct 36 ms 39416 KB Partially correct
21 Correct 37 ms 39540 KB Output is correct
22 Partially correct 37 ms 39416 KB Partially correct
23 Partially correct 37 ms 39416 KB Partially correct
24 Correct 37 ms 39416 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 71 ms 40780 KB Partially correct
2 Incorrect 128 ms 41268 KB Output isn't correct
3 Partially correct 77 ms 40792 KB Partially correct
4 Incorrect 95 ms 41416 KB Output isn't correct
5 Correct 84 ms 40688 KB Output is correct
6 Correct 79 ms 40860 KB Output is correct
7 Partially correct 104 ms 40912 KB Partially correct
8 Partially correct 96 ms 41024 KB Partially correct
9 Correct 92 ms 41412 KB Output is correct
10 Partially correct 231 ms 45540 KB Partially correct
11 Incorrect 133 ms 42316 KB Output isn't correct
12 Partially correct 145 ms 43040 KB Partially correct
13 Incorrect 142 ms 42648 KB Output isn't correct
14 Correct 120 ms 42020 KB Output is correct
15 Partially correct 164 ms 43128 KB Partially correct
16 Correct 181 ms 43368 KB Output is correct
17 Partially correct 160 ms 43000 KB Partially correct
18 Incorrect 156 ms 42872 KB Output isn't correct
19 Partially correct 193 ms 44208 KB Partially correct
20 Correct 296 ms 46756 KB Output is correct
21 Correct 211 ms 44584 KB Output is correct
22 Partially correct 177 ms 43932 KB Partially correct
23 Correct 226 ms 44536 KB Output is correct
24 Partially correct 211 ms 44368 KB Partially correct
25 Correct 204 ms 44152 KB Output is correct
26 Correct 196 ms 44024 KB Output is correct
27 Partially correct 224 ms 44408 KB Partially correct
28 Correct 252 ms 44508 KB Output is correct
29 Partially correct 238 ms 45304 KB Partially correct
30 Correct 341 ms 47492 KB Output is correct
31 Incorrect 248 ms 45364 KB Output isn't correct
32 Partially correct 228 ms 44408 KB Partially correct
33 Correct 296 ms 44608 KB Output is correct
34 Correct 255 ms 44868 KB Output is correct
35 Correct 220 ms 44664 KB Output is correct
36 Incorrect 243 ms 44852 KB Output isn't correct
37 Correct 270 ms 45528 KB Output is correct
38 Partially correct 279 ms 45432 KB Partially correct
39 Partially correct 295 ms 45620 KB Partially correct
40 Correct 337 ms 47088 KB Output is correct
41 Partially correct 427 ms 49400 KB Partially correct