oj.uz

Submission #126330

# Submission time Handle Problem Language Result Execution time Memory
126330 2019-07-07T12:06:52 Z eriksuenderhauf 007 (CEOI14_007) C++11
0 / 100
 361 ms 37680 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 (a2.fi == a2.se)
			ans = min(ans, min(a2.se - a1.fi, a2.fi - a1.se));
	}
	
	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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27768 KB Output is correct
2 Correct 27 ms 27768 KB Output is correct
3 Correct 34 ms 27644 KB Output is correct
4 Incorrect 27 ms 27640 KB Output isn't correct
5 Incorrect 27 ms 27768 KB Output isn't correct
6 Correct 28 ms 27768 KB Output is correct
7 Correct 27 ms 27768 KB Output is correct
8 Incorrect 29 ms 27768 KB Output isn't correct
9 Correct 29 ms 27772 KB Output is correct
10 Correct 27 ms 27768 KB Output is correct
11 Correct 27 ms 27768 KB Output is correct
12 Incorrect 27 ms 27768 KB Output isn't correct
13 Correct 28 ms 27768 KB Output is correct
14 Incorrect 27 ms 27768 KB Output isn't correct
15 Correct 27 ms 27768 KB Output is correct
16 Incorrect 28 ms 27768 KB Output isn't correct
17 Incorrect 28 ms 27768 KB Output isn't correct
18 Incorrect 27 ms 27768 KB Output isn't correct
19 Correct 28 ms 27896 KB Output is correct
20 Correct 30 ms 27768 KB Output is correct
21 Correct 27 ms 27768 KB Output is correct
22 Correct 28 ms 27796 KB Output is correct
23 Correct 28 ms 27768 KB Output is correct
24 Incorrect 28 ms 27768 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 29176 KB Output is correct
2 Incorrect 91 ms 29816 KB Output isn't correct
3 Correct 57 ms 29432 KB Output is correct
4 Incorrect 77 ms 30072 KB Output isn't correct
5 Correct 54 ms 29224 KB Output is correct
6 Correct 57 ms 29432 KB Output is correct
7 Correct 62 ms 29472 KB Output is correct
8 Correct 63 ms 29560 KB Output is correct
9 Incorrect 180 ms 29928 KB Output isn't correct
10 Correct 220 ms 34400 KB Output is correct
11 Incorrect 95 ms 30840 KB Output isn't correct
12 Correct 118 ms 31480 KB Output is correct
13 Incorrect 106 ms 31096 KB Output isn't correct
14 Correct 96 ms 30584 KB Output is correct
15 Correct 129 ms 31736 KB Output is correct
16 Correct 134 ms 31736 KB Output is correct
17 Correct 154 ms 31352 KB Output is correct
18 Incorrect 120 ms 31480 KB Output isn't correct
19 Correct 161 ms 32528 KB Output is correct
20 Incorrect 262 ms 35240 KB Output isn't correct
21 Incorrect 172 ms 33020 KB Output isn't correct
22 Correct 161 ms 32376 KB Output is correct
23 Correct 179 ms 32864 KB Output is correct
24 Correct 165 ms 32816 KB Output is correct
25 Incorrect 149 ms 32504 KB Output isn't correct
26 Correct 159 ms 32348 KB Output is correct
27 Correct 176 ms 32860 KB Output is correct
28 Correct 193 ms 33016 KB Output is correct
29 Correct 192 ms 33732 KB Output is correct
30 Incorrect 276 ms 35736 KB Output isn't correct
31 Incorrect 195 ms 33656 KB Output isn't correct
32 Correct 186 ms 32832 KB Output is correct
33 Correct 162 ms 33024 KB Output is correct
34 Incorrect 188 ms 33272 KB Output isn't correct
35 Incorrect 183 ms 33144 KB Output isn't correct
36 Incorrect 186 ms 33448 KB Output isn't correct
37 Correct 214 ms 34040 KB Output is correct
38 Correct 210 ms 33788 KB Output is correct
39 Correct 225 ms 33908 KB Output is correct
40 Incorrect 263 ms 35580 KB Output isn't correct
41 Correct 361 ms 37680 KB Output is correct