oj.uz

Submission #126333

# Submission time Handle Problem Language Result Execution time Memory
126333 2019-07-07T12:11:17 Z eriksuenderhauf 007 (CEOI14_007) C++11
30 / 100
 361 ms 37628 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[MAXN];
vi adj[MAXN];

pii bfs(int src, int x, int y, int p = 0) {
	deque<int> pq;
	mem(dp, 0x3f);
	dp[src] = 0;
	dp[p] = 0;
	pq.pb(src);
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		for (int v: adj[u]) {
			if (dp[v] != 1061109567)
				continue;
			dp[v] = dp[u] + 1;
			pq.pb(v);
		}
	}
	return mp(dp[x], dp[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);
	pii a2 = bfs(d, a, b);
	pii a3 = bfs(d, a, b, s);
	//cerr << a1.fi << "/" << a2.fi << " | " << a1.se << "/" << a2.se << "\n";
	int ans = min(a2.fi - a1.fi, a2.se - a1.se);
	if (a2 == a3) {
		if (a1.fi == a1.se && ans > 0)
			ans--;
	}
	
	if (ans < 0) ans = -1;
	pri(ans);
    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:60: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:63: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
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27768 KB Output is correct
2 Correct 33 ms 27768 KB Output is correct
3 Correct 27 ms 27640 KB Output is correct
4 Correct 27 ms 27768 KB Output is correct
5 Correct 34 ms 27768 KB Output is correct
6 Correct 29 ms 27768 KB Output is correct
7 Partially correct 27 ms 27768 KB Partially correct
8 Correct 27 ms 27768 KB Output is correct
9 Partially correct 27 ms 27768 KB Partially correct
10 Correct 26 ms 27768 KB Output is correct
11 Partially correct 32 ms 27768 KB Partially correct
12 Correct 33 ms 27768 KB Output is correct
13 Partially correct 29 ms 27768 KB Partially correct
14 Correct 27 ms 27768 KB Output is correct
15 Partially correct 28 ms 27768 KB Partially correct
16 Correct 28 ms 27768 KB Output is correct
17 Correct 27 ms 27768 KB Output is correct
18 Correct 27 ms 27768 KB Output is correct
19 Partially correct 27 ms 27768 KB Partially correct
20 Partially correct 28 ms 27768 KB Partially correct
21 Correct 28 ms 27768 KB Output is correct
22 Partially correct 28 ms 27768 KB Partially correct
23 Correct 28 ms 27868 KB Output is correct
24 Correct 28 ms 27768 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 55 ms 29068 KB Partially correct
2 Correct 74 ms 29532 KB Output is correct
3 Partially correct 58 ms 29020 KB Partially correct
4 Correct 69 ms 29560 KB Output is correct
5 Correct 55 ms 28892 KB Output is correct
6 Correct 55 ms 29176 KB Output is correct
7 Partially correct 74 ms 29432 KB Partially correct
8 Partially correct 61 ms 29304 KB Partially correct
9 Correct 75 ms 29688 KB Output is correct
10 Partially correct 207 ms 33912 KB Partially correct
11 Correct 92 ms 30584 KB Output is correct
12 Partially correct 112 ms 31224 KB Partially correct
13 Correct 98 ms 30904 KB Output is correct
14 Correct 121 ms 30328 KB Output is correct
15 Partially correct 115 ms 31352 KB Partially correct
16 Correct 126 ms 31608 KB Output is correct
17 Partially correct 115 ms 31096 KB Partially correct
18 Correct 132 ms 31208 KB Output is correct
19 Partially correct 153 ms 32376 KB Partially correct
20 Correct 260 ms 35036 KB Output is correct
21 Correct 166 ms 32760 KB Output is correct
22 Partially correct 151 ms 32008 KB Partially correct
23 Correct 153 ms 32632 KB Output is correct
24 Partially correct 145 ms 32632 KB Partially correct
25 Correct 152 ms 32376 KB Output is correct
26 Correct 139 ms 32120 KB Output is correct
27 Partially correct 248 ms 32760 KB Partially correct
28 Partially correct 178 ms 32868 KB Partially correct
29 Partially correct 217 ms 33496 KB Partially correct
30 Correct 280 ms 35608 KB Output is correct
31 Correct 204 ms 33528 KB Output is correct
32 Partially correct 173 ms 32632 KB Partially correct
33 Correct 151 ms 32804 KB Output is correct
34 Correct 186 ms 33252 KB Output is correct
35 Correct 173 ms 32860 KB Output is correct
36 Correct 195 ms 33144 KB Output is correct
37 Correct 221 ms 33784 KB Output is correct
38 Partially correct 209 ms 33656 KB Partially correct
39 Partially correct 293 ms 33672 KB Partially correct
40 Correct 306 ms 35448 KB Output is correct
41 Partially correct 361 ms 37628 KB Partially correct