oj.uz

Submission #391832

# Submission time Handle Problem Language Result Execution time Memory
391832 2021-04-20T03:26:56 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
20 / 100
 283 ms 17476 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 200010, inf = 1e9;

int n, m, s, d, A, B;
vector<int> edge[MAX_N];

int diss[MAX_N], disd[MAX_N], disa[MAX_N], disb[MAX_N];

void get_dis(int s, int *dis) {
	fill(dis, dis + n + 1, inf);

	queue<int> q;
	q.emplace(s); dis[s] = 0;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int u : edge[x])
			if (chmin(dis[u], dis[x] + 1))
				q.emplace(u);
	}
}
bool valid(int rest) {
	auto test = [&](int x) {
		int art = diss[x] + rest;
		int ga = art + disa[x], gb = art + disb[x];
		if (max(disa[x], disb[x]) > 1) return false;

		int da = disd[A], db = disd[B];

		if (min(disa[x], disb[x]) == 1) {
			if (art <= min(da, db)) return true;
			return false;
		}

		if (ga <= da && gb <= db) return true;

		return false;
	};

	for (int i = 1;i <= n;++i)
		if (test(i)) return true;
	return false;

}
	
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> s >> d >> A >> B;
	for (int a, b, i = 0;i < m;++i) {
		cin >> a >> b;
		DE(a, b);
		edge[a].pb(b), edge[b].pb(a);
	}
	get_dis(s, diss), get_dis(d, disd);
	get_dis(A, disa), get_dis(B, disb);

	if (!valid(0)) return puts("-1"), 1;

	int l = 0, r = n, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (valid(mid+1))
			l = mid + 1;
		else
			r = mid;
	}
	cout << l << '\n';
}

Compilation message

007.cpp: In function 'int32_t main()':
007.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
007.cpp:66:3: note: in expansion of macro 'DE'
   66 |   DE(a, b);
      |   ^~
007.cpp:76:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   mid = l + r >> 1;
      |         ~~^~~

Subtask #1
6.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Runtime error 3 ms 4940 KB Execution failed because the return code was nonzero
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Partially correct 3 ms 4940 KB Partially correct
7 Partially correct 3 ms 4940 KB Partially correct
8 Correct 3 ms 4940 KB Output is correct
9 Partially correct 3 ms 4940 KB Partially correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Partially correct 4 ms 4940 KB Partially correct
14 Correct 5 ms 4940 KB Output is correct
15 Partially correct 4 ms 4940 KB Partially correct
16 Correct 5 ms 4940 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Partially correct 4 ms 5068 KB Partially correct
20 Partially correct 4 ms 5068 KB Partially correct
21 Correct 4 ms 4940 KB Output is correct
22 Partially correct 4 ms 5068 KB Partially correct
23 Partially correct 4 ms 5068 KB Partially correct
24 Correct 4 ms 5068 KB Output is correct

Subtask #2
14.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 6820 KB Partially correct
2 Correct 33 ms 7816 KB Output is correct
3 Partially correct 28 ms 6988 KB Partially correct
4 Correct 42 ms 7892 KB Output is correct
5 Correct 32 ms 6732 KB Output is correct
6 Correct 26 ms 7096 KB Output is correct
7 Partially correct 31 ms 7236 KB Partially correct
8 Partially correct 32 ms 7240 KB Partially correct
9 Correct 49 ms 7752 KB Output is correct
10 Partially correct 157 ms 12088 KB Partially correct
11 Correct 58 ms 9200 KB Output is correct
12 Partially correct 112 ms 10300 KB Partially correct
13 Correct 83 ms 9628 KB Output is correct
14 Runtime error 51 ms 8800 KB Execution failed because the return code was nonzero
15 Partially correct 80 ms 10436 KB Partially correct
16 Correct 84 ms 10740 KB Output is correct
17 Partially correct 88 ms 10120 KB Partially correct
18 Correct 79 ms 10052 KB Output is correct
19 Partially correct 105 ms 11336 KB Partially correct
20 Correct 188 ms 14120 KB Output is correct
21 Correct 115 ms 12580 KB Output is correct
22 Partially correct 130 ms 11468 KB Partially correct
23 Correct 124 ms 12496 KB Output is correct
24 Partially correct 107 ms 12408 KB Partially correct
25 Correct 110 ms 11980 KB Output is correct
26 Correct 98 ms 11516 KB Output is correct
27 Partially correct 122 ms 12484 KB Partially correct
28 Partially correct 141 ms 12448 KB Partially correct
29 Partially correct 156 ms 12956 KB Partially correct
30 Correct 206 ms 14916 KB Output is correct
31 Correct 134 ms 13664 KB Output is correct
32 Partially correct 134 ms 12536 KB Partially correct
33 Correct 126 ms 12688 KB Output is correct
34 Correct 154 ms 13080 KB Output is correct
35 Correct 172 ms 12740 KB Output is correct
36 Correct 127 ms 13200 KB Output is correct
37 Correct 154 ms 14148 KB Output is correct
38 Partially correct 158 ms 13904 KB Partially correct
39 Partially correct 208 ms 13916 KB Partially correct
40 Correct 237 ms 15404 KB Output is correct
41 Partially correct 283 ms 17476 KB Partially correct