oj.uz

Submission #126327

# Submission time Handle Problem Language Result Execution time Memory
126327 2019-07-07T12:02:16 Z eriksuenderhauf 007 (CEOI14_007) C++11
30 / 100
 481 ms 37548 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);
	//cerr << a1.fi << "/" << a2.fi << " | " << a1.se << "/" << a2.se << "\n";
	int ans = min(a2.fi - a1.fi, a2.se - a1.se);
	 {
		pii a3 = bfs(d, a, b, s);
		if (a2 == a3)
			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 Partially correct 27 ms 27640 KB Partially correct
2 Partially correct 27 ms 27640 KB Partially correct
3 Partially correct 27 ms 27640 KB Partially correct
4 Correct 27 ms 27640 KB Output is correct
5 Correct 27 ms 27768 KB Output is correct
6 Correct 27 ms 27768 KB Output is correct
7 Partially correct 27 ms 27640 KB Partially correct
8 Correct 27 ms 27640 KB Output is correct
9 Partially correct 24 ms 27768 KB Partially correct
10 Partially correct 28 ms 27640 KB Partially correct
11 Partially correct 27 ms 27768 KB Partially correct
12 Correct 28 ms 27740 KB Output is correct
13 Partially correct 27 ms 27768 KB Partially correct
14 Correct 28 ms 27768 KB Output is correct
15 Partially correct 27 ms 27768 KB Partially correct
16 Correct 28 ms 27768 KB Output is correct
17 Correct 27 ms 27668 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 27740 KB Partially correct
21 Partially correct 27 ms 27768 KB Partially correct
22 Partially correct 28 ms 27768 KB Partially correct
23 Correct 27 ms 27768 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 28920 KB Partially correct
2 Correct 73 ms 29564 KB Output is correct
3 Partially correct 58 ms 29048 KB Partially correct
4 Correct 92 ms 29664 KB Output is correct
5 Partially correct 57 ms 28920 KB Partially correct
6 Partially correct 73 ms 29176 KB Partially correct
7 Partially correct 61 ms 29176 KB Partially correct
8 Partially correct 63 ms 29176 KB Partially correct
9 Correct 76 ms 29708 KB Output is correct
10 Partially correct 208 ms 33932 KB Partially correct
11 Correct 110 ms 30584 KB Output is correct
12 Partially correct 124 ms 31224 KB Partially correct
13 Correct 103 ms 30712 KB Output is correct
14 Correct 93 ms 30328 KB Output is correct
15 Partially correct 124 ms 31352 KB Partially correct
16 Partially correct 136 ms 31608 KB Partially correct
17 Partially correct 140 ms 31096 KB Partially correct
18 Correct 119 ms 31156 KB Output is correct
19 Partially correct 151 ms 32348 KB Partially correct
20 Correct 266 ms 35064 KB Output is correct
21 Correct 174 ms 32888 KB Output is correct
22 Partially correct 152 ms 32104 KB Partially correct
23 Partially correct 162 ms 32708 KB Partially correct
24 Partially correct 160 ms 32764 KB Partially correct
25 Correct 148 ms 32424 KB Output is correct
26 Partially correct 153 ms 32184 KB Partially correct
27 Partially correct 175 ms 32808 KB Partially correct
28 Partially correct 190 ms 32716 KB Partially correct
29 Partially correct 188 ms 33528 KB Partially correct
30 Correct 283 ms 35576 KB Output is correct
31 Correct 232 ms 33528 KB Output is correct
32 Partially correct 179 ms 32604 KB Partially correct
33 Partially correct 172 ms 33004 KB Partially correct
34 Correct 194 ms 33144 KB Output is correct
35 Correct 481 ms 33004 KB Output is correct
36 Correct 258 ms 33208 KB Output is correct
37 Partially correct 202 ms 33788 KB Partially correct
38 Partially correct 224 ms 33676 KB Partially correct
39 Partially correct 233 ms 33656 KB Partially correct
40 Correct 269 ms 35320 KB Output is correct
41 Partially correct 360 ms 37548 KB Partially correct